Art Gallery Localization

Abstract

We study the problem of placing a set $T$ of broadcast towers in a simple polygon $P$ in order for any point to locate itself in the interior of $P$. Let $V(p)$ denote the visibility polygon of a point $p$, as the set of all points $q\in P$ that are visible to $p$. For any point $p\in P$: for each tower $t\in T\cap V(p)$ the point $p$ receives the coordinates of $t$ and the Euclidean distance between $t$ and $p$. From this information $p$ can determine its coordinates. We show a tower-positioning algorithm that computes such a set $T$ of size at most $\lfloor 2n/3\rfloor$, where $n$ is the size of $P$. This improves the previous upper bound of $\lfloor 8n/9\rfloor$ towers. We also show that $\lfloor 2n/3\rfloor$ towers are sometimes necessary.

21 pages, 34 figures, submitted to the Journal of Computational Geometry: Theory and Applications

References in corpus (2)

• Detecting Weakly Simple Polygons
• Irrational Guards are Sometimes Needed