Annals of Computer Science and Information Systems, Volume 21

DOI: http://dx.doi.org/10.15439/2020F79

Citation: Proceedings of the 2020 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 21, pages 215–222 (2020)

Full text

Abstract. 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.

References

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.