Lower Bound for Sculpture Garden Problem: Localization of IoT Devices
Source abstract
Abstract
The purpose of the current study is to investigate a special case of art gallery problem, namely a sculpture garden problem. In this problem, for a given polygon P, the ultimate goal is to place the minimum number of guards (landmarks) to define the interior polygon P by applying a monotone Boolean formula composed of the guards. Using this problem, it can replace the operation-based method with time-consuming, pixel-based algorithms. So, the processing time of some problems in the fields of machine vision, image processing and gamification can be strongly reduced. The problem has also many applications in mobile device localization in the Internet of Things (IoT). An open problem in this regard is the proof of Eppstein’s conjecture, which has remained an open problem since 2007. According to his conjecture, in the worst case, n−2 vertex guards are required to describe any n-gon. In this paper, a lower bound is introduced for the special case of this problem (natural vertex guard), which shows that if a polygon can be defined with natural vertex guards, then n−2 is a lower bound.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Computational Geometry and Mesh Generation · Smart Parking Systems Research · Robotic Path Planning Algorithms
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Department of Computer Science, New Jersey Institute of Technology, Newark, NJ 07102, USA
Department of Computer Science, Faculty of Mathematical Sciences, Alzahra University, Tehran 1993893973, Iran
Institute for Advanced Studies in Basic Sciences (IASBS), Zanjan 45137-66731, Iran
Department of Quantitative Studies, University Canada West, Vancouver, BC V6Z 0E5, Canada
References (19)
Show source-provided references
1. De Berg, M., Van Kreveld, M., Overmars, M., and Schwarzkopf, O.C. (2000). Computational Geometry, Springer.10.1007/978-3-662-04245-8 ↗
2. Eppstein, D., Goodrich, M.T., and Sitchinava, N. (2007). Proceedings of the Twenty-Third Annual Symposium on Computational Geometry, ACM.
3. Eppstein, D., Goodrich, M.T., and Sitchinava, N. (2006). Guard placement for wireless localization. arXiv.
4. Christ, T., Hoffmann, M., and Okamoto, Y. (2009). Abstracts 25th European Workshop Computational Geometry, Citeseer.
5. Christ, T., and Hoffmann, M. (2009). CCCG, Citeseer.
6. Dobkin, D., Guibas, L., Hershberger, J., and Snoeyink, J. (1988). An Efficient Algorithm for Finding the CSG Representation of a Simple Polygon, ACM.10.1145/54852.378472 ↗
7. The prison yard problem10.1007/BF01212977 ↗
8. Illumination of polygons with vertex lights10.1016/0020-0190(95)00129-Z ↗
9. Illumination by floodlights10.1016/S0925-7721(97)00027-8 ↗
10. Modem illumination of monotone polygons10.1016/j.comgeo.2017.05.010 ↗
11. Coverage with k-transmitters in the presence of obstacles10.1007/s10878-012-9475-x ↗
12. Crepaldi, B.E., de Rezende, P.J., and de Souza, C.C. (2013). CCCG, Carleton University.
13. Solving the natural wireless localization problem to optimality efficiently10.1016/j.comgeo.2014.12.004 ↗
14. A tight bound for point guards in piecewise convex art galleries10.1016/j.comgeo.2013.04.004 ↗
15. Guarding curvilinear art galleries with vertex or point guards10.1016/j.comgeo.2008.11.002 ↗
16. Guarding curvilinear art galleries with edge or mobile guards via 2-dominance of triangulation graphs10.1016/j.comgeo.2010.07.002 ↗
17. Damian, M., Flatland, R., O’Rourke, J., and Ramaswami, S. (2007). A new lower bound on guard placement for wireless localization. arXiv.
18. Christ, T., Hoffmann, M., Okamoto, Y., and Uno, T. (2008). Algorithm Theory-SWAT, Springer.
19. On the Number of Guards in sculpture garden problem