Optimal Art Gallery Localization is NP-hard
Art Gallery Localization (AGL) is the problem of placing a set T of broadcast towers in a simple polygon P in order for a point to locate itself in the interior. For any point p∈P: for each tower t∈T∩V(p) (where V(p) denotes the visibility polygon of 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 study the computational complexity of AGL problem. We show that the problem of determining the minimum number of broadcast towers that can localize a point anywhere in a simple polygon P is NP-hard. We show a reduction from Boolean Three Satisfiability problem to our problem and give a proof that the reduction takes polynomial time.
|Keywords||Art gallery, GPS, Localization, Polygon partition, Trilateration|
Bose, P, De Carufel, J.-L. (Jean-Lou), Shaikhet, A. (Alina), & Smid, M. (2020). Optimal Art Gallery Localization is NP-hard. Computational Geometry, 88. doi:10.1016/j.comgeo.2020.101607