Um Algoritmo Eficiente para o Problema do Posicionamento Natural de Antenas
Abstract
Considered a variation of the art gallery problem, the wireless localization problem deals with the placement of the smallest number of broadcastin antennas required to determine if a person is inside or outside the gallery. Each antenna propagates a unique key within a certain antenna-specific angle of broadcast, and the set of keys received at any given point must be sufficient to determine whether that point belongs or not to the polygon representing the gallery. To ascertain this localization property, a Boolean formula must be produced along with the placement of the antennas. In this thesis, we present an exact algorithm based on integer linear programming and geometrical properties for solving the natural wireless localization problem, which is known to be NP-hard. The efficiency of the algorithm is certified by experimental results comprising the solutions of 720 instances, including polygon with holes with up to 1000 vertices, in less than six minutes on a standard desktop computer.
References
Christ, T. and Hoffmann, M. (2009). Wireless localization with vertex guards is NP-hard. In 21st Canadian Conference on Computational Geometry, pages 149–152, Toronto.
Christ, T., Hoffmann, M., and Okamoto, Y. (2009). Natural wireless localization is NPhard. In Abstracts 25th European Workshop on Comp. Geometry, pages 175–178, Bruxelles.
Christ, T., Hoffmann, M., Okamoto, Y., and Uno, T. (2008). Improved bounds for wireless localization. In Algorithm Theory - SWAT 2008, volume 5124 of Lect. Notes in Comp. Science, pages 77–89, Goteborg. Springer Berlin Heidelberg.
Couto, M. C., de Souza, C. C., and de Rezende, P. J. (2008). Experimental evaluation of an exact algorithm for the orthogonal art gallery problem. In Experimental Algorithms, 7th International Workshop, WEA 2008, Provincetown, MA, USA, May 30-June 1, 2008, Proceedings, volume 5038 of Lect. Notes in Comp. Science, pages 101–113.
Couto, M. C., de Souza, C. C., and de Rezende, P. J. (2011). An exact algorithm for minimizing vertex guards on art galleries. Int. Trans. in Oper. Research, 18:425–448.
Crepaldi, B. E., de Rezende, P. J., and de Souza, C. C. (2013a). An efficient exact algorithm for the natural wireless localization problem. In 25th Canadian Conference on Computational Geometry, Waterloo, Ontario, August 8-10.
Crepaldi, B. E., de Rezende, P. J., and de Souza, C. C. (2013b). TheWireless Localization project. www.ic.unicamp.br/cid/Problem-instances/Wireless-Localization.
Crepaldi, B. E., de Rezende, P. J., and de Souza, C. C. (2015). Solving the natural wireless localization problem to optimality efficiently. Comp. Geom. and Appl., 48(5):370–379.
Dey, T. K. (1991). Triangulation and CSG representation of polyhedra with arbitrary genus. In Seventh Annual Symposium on Computational Geometry, pages 364–371.
Dobkin, D., Guibas, L., Hershberger, J., and Snoeyink, J. (1993). An efficient algorithm for finding the CSG representation of a simple polygon. Algorithmica, 10(1):1–23.
Eppstein, D., Goodrich, M. T., and Sitchinava, N. (2007). Guard placement for efficient point-in-polygon proofs. In 23rd Annual Symp. on Comp. Geom., pages 27–36.
O’Rourke, J. (1987). Art gallery theorems and algorithms. Oxford University Press, Inc., New York.
Urrutia, J. (2000). Art gallery and illumination problems. In Handbook of Computational Geometry, pages 973–1027. North-Holland.
