Art Gallery Trilateration Problem

Alina Shaikhet

Trilateration is the technique of determining absolute locations of points using distances and the geometry of circles and spheres. We study the problem of placing distance-measuring guards (towers) in a simple polygon in order to locate points in the interior. We show that in any polygonal art gallery of \(n\) sides it is possible to place \(\lfloor \frac{2n}{3} \rfloor\) towers so that every interior point of the gallery can be trilaterated/located without ambiguities. This improves the previous best upper bound of \(\frac{8n}{9}\) by M. Dippel and R. Sundaram presented at CCCG 2015. We also show that in some cases \(\lfloor \frac{2n}{3} \rfloor\) towers are necessary.