An Exact Two-Phase Method For Optimal Camera Placement In Art Gallery Problem

• Autorzy: Alihodzic Adis , Delalic Sead , Hasic Damir

Identyfikatory

DOI

10.15439/2020F79

• Konferencja: Federated Conference on Computer Science and Information Systems (15 ; 06-09.09.2020 ; Sofia, Bulgaria)
• Języki publikacji: EN

Abstrakty

EN

It is well-known that determining the optimal number of guards which can cover the interior of a simple nonconvex polygon presents an NP-hard problem. The optimal guard placement can be described as a problem which seeks for the smallest number of guards required to cover every point in a complex environment. In this paper, we propose an exact twophase method as well as an approximate method for tackling the mentioned issue. The proposed exact approach in the first phase maps camera placement problem to the set covering problem, while in the second phase it uses famous state-of-the-art CPLEX solver to address set covering problem. The performance of our combined exact algorithm was compared to the performance of the approximate one. According to the results presented in the experimental analysis, it can be seen that the exact approach outperforms the approximate method for all instances.

Słowa kluczowe

EN

approximation theory; computational complexity; computational geometry; optimisation

PL

teoria aproksymacji; złożoność obliczeniowa; geometria obliczeniowa; optymalizacja

• Wydawca: Polskie Towarzystwo Informatyczne
• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2020
• Tom: Vol. 21
• Strony: 215--222
• Opis fizyczny: Bibliogr. 25 poz., il., tab.

Twórcy

autor

Alihodzic Adis

• University of Sarajevo, BiH Department of Mathematics ul. Zmaja od Bosne, 33-35, Sarajevo

autor

Delalic Sead

• University of Sarajevo, BiH Department of Mathematics ul. Zmaja od Bosne, 33-35, Sarajevo

autor

Hasic Damir

• University of Sarajevo, BiH Department of Mathematics ul. Zmaja od Bosne, 33-35, Sarajevo

Bibliografia

• 1. E. Tuba, I. Tuba, D. Dolicanin-Djekic, A. Alihodzic, and M. Tuba, “Efficient drone placement for wireless sensor networks coverage by bare bones fireworks algorithm,” in 2018 6th International Symposium on Digital Forensic and Security (ISDFS), 2018. doi: https://doi.org/10.1109/ISDFS.2018.8355349 pp. 1–5.
• 2. E. Tuba, R. Capor-Hrosik, A. Alihodzic, and M. Tuba, “Drone placement for optimal coverage by brain storm optimization algorithm,” in Hybrid Intelligent Systems. Cham: Springer International Publishing, 2018. http://dx.doi.org/https://doi.org/10.1007/978-3-319-76351-4%5F17 pp. 167–176.
• 3. A. Elnagar and L. Lulu, “An art gallery-based approach to autonomous robot motion planning in global environments,” in 2005 IEEE/RSJ International Conference on Intelligent Robots and Systems, 2005, pp. 2079–2084.
• 4. J. O’Rourke, Art Gallery Theorems and Algorithms. Oxford University Press, 1987.
• 5. J. O’Rourke and K. Supowit, “Some np-hard polygon decomposition problems,” IEEE Transactions on Information Theory, vol. 29, no. 2, pp. 181–190, March 1983. http://dx.doi.org/https://10.1109/TIT.1983.1056648
• 6. D. Lee and A. Lin, “Computational complexity of art gallery problems,” IEEE Transactions on Information Theory, vol. 32, no. 2, pp. 276–282, 1986. http://dx.doi.org/https://10.1109/TIT.1986.1057165
• 7. M. J. Katz and G. S. Roisman, “On guarding the vertices of rectilinear domains,” Computational Geometry, vol. 39, no. 3, pp. 219 – 228, 2008. http://dx.doi.org/https://doi.org/10.1016/j.comgeo.2007.02.002
• 8. D. Schuchardt and H. Hecker, “Two np-hard art-gallery problems for ortho-polygons,” Mathematical Logic Quarterly, vol. 41, no. 2, pp. 261 – 267, 1995. http://dx.doi.org/https://
• 9. V. Chvátal, “A combinatorial theorem in plane geometry,” Journal of Combinatorial Theory, Series B, vol. 18, no. 1, pp. 39 – 41, 1975. http://dx.doi.org/https://doi.org/10.1016/0095-8956(75)90061-1
• 10. I. Bjorling-Sachs and D. L. Souvaine, “An efficient algorithm for guard placement in polygons with holes,” Discrete & Computational Geometry, vol. 13, p. 77–109, January 1995. doi: https://doi.org/10.1007/BF02574029
• 11. F. Hoffmann, M. Kaufmann, and K. Kriegel, “The art gallery theorem for polygons with holes,” in [1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science, October 1991. doi: https://10.1109/SFCS.1991.185346 pp. 39–48.
• 12. E. Györi, F. Hoffmann, K. Kriegel, and T. Shermer, “Generalized guarding and partitioning for rectilinear polygons,” Computational Geometry, vol. 6, no. 1, pp. 21 – 44, 1996. http://dx.doi.org/https://doi.org/10.1016/0925-7721(96)00014-4
• 13. S. Fisk, “A short proof of chvátal’s watchman theorem,” Journal of Combinatorial Theory, Series B, vol. 24, no. 3, p. 374, 1978. doi: https://doi.org/10.1016/0095-8956(78)90059-X
• 14. CPLEX, IBM ILOG CPLEX Optimization Studio CPLEX User’s Manual V 12.7. International Business Machines Corporation, 2017. [Online]. Available: https://www.ibm.com/support/knowledgecenter/SSSA5P_12.7.1/ilog.odms.studio.help/pdf/usrcplex.pdf
• 15. M. R. Garey and D. S. Johnson, Computers and Intractability; A Guide to the Theory of NP-Completeness. USA: W. H. Freeman & Co., 1990. ISBN 0716710455
• 16. E. Balas and A. Ho, Set covering algorithms using cutting planes, heuristics, and subgradient optimization: A computational study. "Springer Berlin Heidelberg, 1980, pp. 37–60. ISBN 978-3-642-00802-3
• 17. T.-P. Shuai and X.-D. Hu, “Connected set cover problem and its applications,” in Algorithmic Aspects in Information and Management. Springer Berlin Heidelberg, 2006. doi: https://doi.org/10.1007/11775096%5F23. ISBN 978-3-540-35158-0 pp. 243–254.
• 18. M. L. Fisher and P. Kedia, “Optimal solution of set covering/partitioning problems using dual heuristics,” Management Science, vol. 36, no. 6, pp. 674–688, 1990. http://dx.doi.org/https://doi.org/10.1287/mnsc.36.6.674
• 19. E. Balas and M. C. Carrera, “A dynamic subgradient-based branch-and-bound procedure for set covering,” Operations Research, vol. 44, pp. 875–890, December 1996. http://dx.doi.org/https://doi.org/10.1287/opre.44.6.875
• 20. A. Caprara, P. Toth, and M. Fischetti, “Algorithms for the set covering problem,” Annals of Operations Research, vol. 98, no. 1-4, p. 353–371, December 2000. http://dx.doi.org/https://doi.org/10.1023/A:1019225027893
• 21. P. Laborie, J. Rogerie, P. Shaw, and P. Vilím, “Ibm ilog cp optimizer for scheduling,” Constraints, vol. 23, pp. 210–250, April 2018. http://dx.doi.org/https://doi.org/10.1007/s10601-018-9281-x
• 22. J. O’Rourke, Computational Geometry in C. Cambridge University Press, September 1998.
• 23. M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars, Computational geometry: algorithms and applications, 3rd ed. Springer, Berlin, Heidelberg, 2008. ISBN 978-3-540-77973-5
• 24. T. Auer and M. Held, “Heuristics for the generation of random polygons,” August 1996, pp. 38–43.
• 25. S. Sadhu, S. Hazarika, K. K. Jain, S. Basu, and T. De, “Grp_ch heuristic for generating random simple polygon,” in Combinatorial Algorithms. Springer Berlin Heidelberg, 2012. http://dx.doi.org/https://doi.org/10.1007/978-3-642-35926-2978-3-642-35926-2 pp. 293–302.

Uwagi

1. Track 1: Artificial Intelligence

2. Technical Session: 13th International Workshop on Computational Optimization

3. Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).