Vertex guarding for dynamic orthogonal art galleries

DOI10.1142/S0218195921500060zbMATH Open1487.68240arXiv2006.16651OpenAlexW4210635977MaRDI QIDQ5072223FDOQ5072223

Debangshu Banerjee, Rajasekhar Inkulu

Publication date: 26 April 2022

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

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.

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

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

zbMATH Keywords

computational geometryart gallerydynamic algorithms

Mathematics Subject Classification ID

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

Cites Work

• A short proof of Chvatal's Watchman Theorem
• On guarding the vertices of rectilinear domains
• Traditional Galleries Require Fewer Watchmen
• Title not available (Why is that?)
• Title not available (Why is that?)
• Two NP‐Hard Art‐Gallery Problems for Ortho‐Polygons
• An alternative proof of the rectilinear art gallery theorem
• Approximation algorithms for art gallery problems in polygons
• Triangulating a simple polygon in linear time
• Maintaining visibility of a polygon with a moving point of view
• Visibility Algorithms in the Plane
• A combinatorial theorem in plane geometry
• Title not available (Why is that?)
• An efficient algorithm for guard placement in polygons with holes
• Title not available (Why is that?)
• Title not available (Why is that?)
• Dynamic Algorithms for Visibility Polygons in Simple Polygons
• Visibility polygon queries among dynamic polygonal obstacles in plane
• Title not available (Why is that?)
• Maintaining the visibility graph of a dynamic simple polygon
• Fast vertex guarding for polygons with and without holes
• Incremental Algorithms to Update Visibility Polygons
• Approximability of guarding weak visibility polygons

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)