Vertex guarding for dynamic orthogonal art galleries

DOI10.1142/S0218195921500060MaRDI QIDQ5072223zbMATHOpenAlexFDO

Authors Debangshu Banerjee, Rajasekhar Inkulu

Publication date 26 April 2022

Published in International Journal of Computational Geometry & Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2006.16651

zbMATH Keywords

computational geometryart gallerydynamic algorithms

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: We devise an algorithm for surveying a dynamic orthogonal polygonal domain by placing one guard at each vertex in a subset of its vertices, i.e., whenever an orthogonal polygonal domain {cal P'} is modified to result in another orthogonal polygonal domain {cal P}, our algorithm updates the set of vertex guards surveying {cal P'} so that the updated guard set surveys {cal P}. Our algorithm modifies the guard placement in O(k lg{(n+n')}) amortized time while ensuring the updated orthogonal polygonal domain with h holes and n vertices is guarded using at most lfloor (n+2h)/4 floor vertex guards. For the special case of the initial orthogonal polygon being hole-free and each update resulting in a hole-free orthogonal polygon, our guard update algorithm takes O(klg{(n+n')}) worst-case time. Here, n' and n are the number of vertices of the orthogonal polygon before and after the update, respectively; and, k is the sum of |n - n'| and the number of updates to a few structures maintained by our algorithm. Further, by giving a construction, we show it suffices for the algorithm to consider only the case in which the parity of the number of reflex vertices of both {cal P'} and {cal P} are equal.

Recommendations

• How to guard orthogonal polygons: diagonal graphs and vertex covers
• Polygon guarding with orientation
• Orthogonal art galleries, holes, and reflex guards
• Guarding orthogonal prison yards: an upper bound
• COMPUTATIONAL GEOMETRY COLUMN 15

Cites work

• scientific article; zbMATH DE number 4060719 (Why is no real title available?)
• scientific article; zbMATH DE number 4065813 (Why is no real title available?)
• scientific article; zbMATH DE number 177851 (Why is no real title available?)
• scientific article; zbMATH DE number 2079392 (Why is no real title available?)
• scientific article; zbMATH DE number 1424310 (Why is no real title available?)
• A combinatorial theorem in plane geometry
• A short proof of Chvatal's Watchman Theorem
• An alternative proof of the rectilinear art gallery theorem
• An efficient algorithm for guard placement in polygons with holes
• Approximability of guarding weak visibility polygons
• Approximation algorithms for art gallery problems in polygons
• Dynamic algorithms for visibility polygons in simple polygons
• Fast vertex guarding for polygons with and without holes
• Incremental algorithms to update visibility polygons
• Maintaining the visibility graph of a dynamic simple polygon
• Maintaining visibility of a polygon with a moving point of view
• On guarding the vertices of rectilinear domains
• Optimal dynamic vertical ray shooting in rectilinear planar subdivisions
• Traditional Galleries Require Fewer Watchmen
• Triangulating a simple polygon in linear time
• Two NP‐Hard Art‐Gallery Problems for Ortho‐Polygons
• Visibility Algorithms in the Plane
• Visibility polygon queries among dynamic polygonal obstacles in plane

Cited in

(1)

• The smallest art gallery not guarded by every third vertex

This page was built for publication: Vertex guarding for dynamic orthogonal art galleries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5072223)