Um Algoritmo Eficiente para o Problema do Posicionamento Natural de Antenas

• Bruno Crepaldi UNICAMP
• Cid de Souza UNICAMP
• Pedro de Rezende UNICAMP

DOI: https://doi.org/10.5753/ctd.2015.10005

Resumo

Considerado uma variação do problema da galeria de arte, o problema do posicionamento de antenas trata da localização do menor número de antenas requerido para determinar se uma pessoa está dentro ou fora da galeria. Cada antena propaga uma chave única dentro de um ângulo específico de transmissão, e o conjunto de chaves recebidas em um dado ponto deve ser suficiente para decidir se ele pertence ou não ao polígono que representa a galeria. Para verificar esta propriedade de localização, uma fórmula Booleana deve ser produzida junto com o posicionamento das antenas. O problema do posicionamento natural de antenas é NP-difícil. Nesta dissertação, apresentamos um algoritmo exato baseado em programação linear inteira e propriedades geométricas para resolvê-lo. A eficiência do algoritmo é certificada por resultados experimentais que compreendem as soluções ótimas de 720 instâncias, incluindo polígono com buracos de atá 1000 vértices, calculadas em menos de seis minutos em um computador desktop padrão.

Referências

Borrmann, D., de Rezende, P. J., de Souza, C. C., Fekete, S. P., Friedrichs, S., Kröller, A., Nüchter, A., Schmidt, C., and Tozoni, D. C. (2013). Point guards and point clouds: Solving general art gallery problems. In Proceedings of the Twenty-ninth Annual Symposium on Computational Geometry, pages 347–348, New York. ACM.

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.