Logo PTI Logo FedCSIS

Proceedings of the 18th Conference on Computer Science and Intelligence Systems

Annals of Computer Science and Information Systems, Volume 35

A lower bound for proportion of visibility polygon's surface to entire polygon's surface: Estimated by Art Gallery Problem and proven that cannot be greatly improved

, , ,

DOI: http://dx.doi.org/10.15439/2023F4335

Citation: Proceedings of the 18th Conference on Computer Science and Intelligence Systems, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 35, pages 1229–1233 ()

Full text

Abstract. Assuming a bounded polygon and a point inside the polygon or on its boundary, the visibility polygon, also called the visibility region, is a polygon reachable, i.e., visible by straight lines from the point without hitting the polygon's edges or vertices. If the polygon is bounded, then the visibility polygon is bounded, and the proportion of the visibility polygon's surface area to the given polygon's surface area could be enumerated. Many papers investigate applications of the visibility polygons in robotics and computer graphics or focus on computationally effective finding the visibility region for a given polygon. However, surprisingly, there seems to be no work estimating the proportion of a visibility polygon's surface to an entire polygon's surface or its bounds. Thus, in this paper, we search for a lower bound of the surface proportion of a visibility polygon to a given one. Assuming $n$-sided simple polygon, i.e., a polygon without holes and edge intersections, we apply the well-known art gallery problem and derive there is always a point inside the polygon or on its boundary that guarantees the proportion of the visibility polygon's surface to the entire polygon's surface is at least $\frac{1}{\left\lfloor n / 3 \right\rfloor}$. We also show that there are $n$-sided polygons for which the proportion of the visibility polygon's surface to the entire polygon's surface is asymptotically not greater than $\frac{1}{\left\lfloor n / 3 \right\rfloor}$ for any point inside the polygon or on its boundary. So, the lower bound of the proportion of the visibility polygon's surface to the entire polygon's surface, $\frac{1}{\left\lfloor n / 3 \right\rfloor}$, cannot be improved in general.

References

  1. D. Bilò, Y. Disser, M. Mihalák, et al. “Reconstructing visibility graphs with simple robots”. In: Theoretical Computer Science 444 (July 2012), pp. 52–59. http://dx.doi.org/10.1016/j.tcs.2012.01.008.
  2. Sudipto Guha and Samir Khuller. “Greedy Strikes Back: Improved Facility Location Algorithms”. In: Journal of Algorithms 31.1 (Apr. 1999), pp. 228–248. DOI : 10.1006/jagm.1998.0993.
  3. Ram Pandit and Placid M. Ferreira. “Determination of minimum number of sensors and their locations for an automated facility: An algorithmic approach”. In: European Journal of Operational Research 63.2 (Dec. 1992), pp. 231–239. DOI: 10.1016/0377-2217(92)90028-8.
  4. Niall L. Williams, Aniket Bera, and Dinesh Manocha. “Redirected Walking in Static and Dynamic Scenes Using Visibility Polygons”. In: IEEE Transactions on Visualization and Computer Graphics 27.11 (Nov. 2021), pp. 4267–4277. http://dx.doi.org/ 10.1109/tvcg.2021.3106432.
  5. James King. “Fast vertex guarding for polygons with and without holes”. In: Computational Geometry 46.3 (Apr. 2013), pp. 219–231. http://dx.doi.org/10.1016/j.comgeo.2012.07.004.
  6. Tetsuo Asano and Hiroshi Umeo. “Systolic algorithms for computing the visibility polygon and triangulation of a polygonal region”. In: Parallel Computing 6.2 (Feb. 1988), pp. 209–216. http://dx.doi.org/10.1016/0167-8191(88)90085-3.
  7. D.T Lee. “Visibility of a simple polygon”. In: Computer Vision, Graphics, and Image Processing 22.2 (May 1983), pp. 207–221. http://dx.doi.org/10.1016/0734-189x(83)90065-8.
  8. B. Joe and R. B. Simpson. “Corrections to Lee’s visibility polygon algorithm”. In: BIT 27.4 (Dec. 1987), pp. 458–473. http://dx.doi.org/10.1007/bf01937271.
  9. V Chvátal. “A combinatorial theorem in plane geometry”. In: Journal of Combinatorial Theory, Series B 18.1 (Feb. 1975), pp. 39–41. http://dx.doi.org/10.1016/0095-8956(75)90061-1.
  10. Steve Fisk. “A short proof of Chvátal’s Watchman Theorem”. In: Journal of Combinatorial Theory, Series B 24.3 (June 1978), p. 374. http://dx.doi.org/10.1016/0095-8956(78)90059-x.