An efficient algorithm for guard placement in polygons with holes

DOI10.1007/BF02574029zbMath0815.68056MaRDI QIDQ1346129

Diane L. Souvaine, Iliana Bjorling-Sachs

Publication date: 20 March 1995

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/131348

zbMATH Keywords

art-gallery problems

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10)

Related Items (14)

Guarding disjoint triangles and claws in the plane ⋮ Multi-agent deployment for visibility coverage in polygonal environments with holes ⋮ Polygon guarding with orientation ⋮ Vertex Guarding for Dynamic Orthogonal Art Galleries ⋮ Generalized guarding and partitioning for rectilinear polygons ⋮ A nearly optimal algorithm for covering the interior of an art gallery ⋮ Illuminating disjoint line segments in the plane ⋮ A nearly optimal sensor placement algorithm for boundary coverage ⋮ Approximation algorithms for art gallery problems in polygons ⋮ The art gallery theorem for polyominoes ⋮ Illumination in the presence of opaque line segments in the plane ⋮ Edge guards in rectilinear polygons ⋮ Multiple-guard kernels of simple polygons ⋮ Enhanced layered segment trees: a pragmatic data structure for real-time processing of geometric objects

Cites Work

• Unnamed Item
• A short proof of Chvatal's Watchman Theorem
• Compactness via symmetrization
• Some methods for studying stability in isoperimetric type problems

This page was built for publication: An efficient algorithm for guard placement in polygons with holes