Irrational guards are sometimes needed

DOI10.4230/LIPICS.SOCG.2017.3MaRDI QIDQ4580074zbMATH OpenOpenAlexFDO

Authors Mikkel Abrahamsen, Anna Adamaszek, Tillmann Miltzow

Publication date 13 August 2018

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

zbMATH Keywords

art gallery problemcomputational geometryirrational numbers

Mathematics Subject Classification ID

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

Abstract: In this paper we study the art gallery problem, which is one of the fundamental problems in computational geometry. The objective is to place a minimum number of guards inside a simple polygon such that the guards together can see the whole polygon. We say that a guard at position $x$ sees a point $y$ if the line segment $xy$ is fully contained in the polygon. Despite an extensive study of the art gallery problem, it remained an open question whether there are polygons given by integer coordinates that require guard positions with irrational coordinates in any optimal solution. We give a positive answer to this question by constructing a monotone polygon with integer coordinates that can be guarded by three guards only when we allow to place the guards at points with irrational coordinates. Otherwise, four guards are needed. By extending this example, we show that for every $n$, there is polygon which can be guarded by $3n$ guards with irrational coordinates but need $4n$ guards if the coordinates have to be rational. Subsequently, we show that there are rectilinear polygons given by integer coordinates that require guards with irrational coordinates in any optimal solution.

Recommendations

• scientific article; zbMATH DE number 177851
• Traditional Galleries Require Fewer Watchmen
• Guards, Galleries, Fortresses, and the Octoplex
• scientific article; zbMATH DE number 1424310
• Art gallery theorems for guarded guards.

Cited in

(13)

• The complexity of drawing a graph in a polygonal region
• Parameterized Analysis of Art Gallery and Terrain Guarding
• The complexity of drawing a graph in a polygonal region
• Reflective guarding a gallery
• The dispersive art gallery problem
• The parameterized complexity of guarding almost convex polygons
• Topological art in simple galleries
• A practical algorithm with performance guarantees for the art gallery problem
• Robustly guarding polygons
• Visibility extension via reflection
• Guarding offices with maximum dispersion
• Polynomial-time algorithms for contiguous art gallery and related problems
• The point-boundary art gallery problem is \(\exists\mathbb{R}\)-hard

This page was built for publication: Irrational guards are sometimes needed

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