Curved sight lines improve visibility in art gallery polygons
Arithmetic Visibility in Polygons: Curved Sight in the Art Gallery
Computational Geometry
Summary
The classical art gallery problem asks how to place guards so they can see every point inside a polygon using straight lines. This paper studies what happens if guards can see along certain carefully defined curved paths instead. The authors find that curved sight can let a single guard see places that straight sight cannot, but there are geometric and arithmetic limits on when this works. They prove that by allowing more complex curves, any finite set of targets inside a polygon can be seen from any guard position. They also identify special sets of points that need very specific curve shapes to be seen.
What this means in practice
- •For robot navigation teams: Design path-planning algorithms that consider curved sight paths to detect obstacles occluded from straight-line sensors.
- •For computer graphics developers: Implement visibility checks with curved sight arcs to improve rendering and shadow calculations in complex polygonal scenes.
A theory result. No direct application yet.
Authors
Malik Barrett
Abstract
In the classical art gallery problem, a guard sees a target when the segment joining them lies entirely within the polygon. We explore what changes when sight may bend along regular arcs on absolutely irreducible curves, but only those defined by primitive integer polynomials of total degree at most \(d\) and coefficient height at most \(H\). We call such curves admissible sight carriers. Arcs can dramatically improve sight. In a one-sided comb, no straight-line guard sees selected targets in two different teeth, yet a single central guard sees a chosen target in every tooth along parabolic carriers. Sight can also fail in two different ways. Geometrically, the polygon may block every sight arc of the allowed degree between two points. For instance, in an alternating comb, the number of guards needed for a row of targets spanning the comb grows linearly with the number of sides at each fixed degree, even for carriers with arbitrary real coefficients. Arithmetically, no admissible carrier may pass through the points at all. Even in the unit square, at fixed \(d\) and \(H\), the proportion of rational targets that must guard themselves tends to one as the height bound grows. An algebraic target may lie on no rational curve of degree at most \(d\), however large \(H\) is. Both failures can be overcome for finite target sets by allowing the degree and coefficient height to grow. We show that every finite set of algebraic targets in a rational polygon becomes visible from any rational interior guard, with explicit bounds. We also construct, for every \(d\), arbitrarily large Galois orbits in the unit square, all of projective height \(4^{d+1}\), whose points must each guard themselves at degree \(d\) for every \(H\). Yet at degree \(d+1\) and coefficient height one, a single guard sees the whole orbit along \(Z(Y-X^{d+1})\).