An Efficient Exact Algorithm for the Natural Wireless Localization Problem.
Bruno Eiras Crepaldi, Pedro J. de Rezende, Cid C. de Souza · Canadian Conference on Computational Geometry · 2013
Considered a variation of the art gallery problem, the wireless localization problem deals with the placement of the smallest number of broadcasting antennas required to satisfy some property within a given polygon. The case dealt with here consists of antennas that propagate a unique key within a certain antenna-specic angle of broadcast, so that the set of keys received at any given point is sucient to determine whether that point is inside or outside the polygon. To ascertain this localization property, a Boolean formula must be produced along with the placement of the antennas. In this paper, we propose an exact algorithm based on integer linear programming for solving the NP-hard natural wireless localization problem. The eciency of our algorithm is certied by experimental results which include the solution of instances of up to 600 vertices in less than ve minutes on a standard desktop computer.