Hiding people in polygons

DOI10.1007/BF02239742zbMath0675.68070OpenAlexW1581938675MaRDI QIDQ1122366

S. H. Smith

Publication date: 1989

Published in: Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02239742

zbMATH Keywords

polygonvisibilityNP-completeguardingm-convexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computing methodologies and applications (68U99) Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17) Variants of convex sets (star-shaped, ((m, n))-convex, etc.) (52A30)

Related Items (18)

Covering grids and orthogonal polygons with periscope guards ⋮ FO model checking on geometric graphs ⋮ Unnamed Item ⋮ Hiding points in arrangements of segments ⋮ Negative results on characterizing visibility graphs ⋮ Connecting guards with minimum Steiner points inside simple polygons ⋮ On colourability of polygon visibility graphs ⋮ Meeting in a polygon by anonymous oblivious robots ⋮ Computing the maximum clique in the visibility graph of a simple polygon ⋮ Guarding polyhedral terrains ⋮ On recognizing and characterizing visibility graphs of simple polygons ⋮ Characterizing and recognizing weak visibility polygons ⋮ Finding minimum hidden guard sets in polygons --- tight approximability results ⋮ Inapproximability of finding maximum hidden sets on polygons and terrains ⋮ Unnamed Item ⋮ On Colourability of Polygon Visibility Graphs ⋮ Isomorphism of spiral polygons ⋮ Efficient visibility queries in simple polygons

Cites Work

• Unnamed Item
• The combinatorial structure of (\(m,n\))-convex sets
• An alternative proof of the rectilinear art gallery theorem
• Galleries need fewer mobile guards: A variation on Chvatal's theorem
• On gallery watchmen in grids
• A decomposition theorem for m-convex sets
• General decomposition theorems for m-convex sets in the plane
• A short proof of Chvatal's Watchman Theorem
• A combinatorial theorem in plane geometry
• Convexity and a certain property \(P_ m\)
• On sets having finitely many points of local nonconvexity and property \(P_ m\)
• Traditional Galleries Require Fewer Watchmen
• Computational complexity of art gallery problems
• A simple proof of the rectilinear art gallery theorem

This page was built for publication: Hiding people in polygons