Logo PTI Logo FedCSIS

Proceedings of the 21st Conference on Computer Science and Intelligence Systems (FedCSIS)

Annals of Computer Science and Information Systems, Volume 47

Weak segment visibility in simple polygons: A reflex-vertex scanning algorithm with a guaranteed-area lower bound

,

DOI: http://dx.doi.org/10.15439/2026F5997

Citation: Lubomír Štěpánek,

Full text

Abstract. We consider weak visibility from a segment inside a simple polygon \(P\). For a segment \(s \subseteq P\), its weak visibility region \(WVP(s)\) is the set of all points of \(P\) visible from at least one point of \(s\). Our objective is to choose a segment with a provably large weak visibility area. This setting is related to watchman-route and mobile-guard models, but here the route is restricted to a single straight segment and the focus is on guaranteed visible area rather than on full coverage or route-length minimization. Such a model is relevant to line-constrained sensing platforms, including rail-guided inspection devices and fixed-wing or wind-constrained aerial platforms operating along approximately straight sensing paths. Let \(n\_r>0\) denote the number of reflex vertices of \(P\). We prove that there exists a segment \(s \subseteq P\) such that \(\mathrm{area}(WVP(s)) \geq \frac{\mathrm{area}(P)}{n\_r}\). Moreover, if a reflex vertex with maximum visibility area does not already see the entire polygon, then a shortest-path-based segment construction yields the strictly stronger bound \(\mathrm{area}(WVP(s)) > \frac{\mathrm{area}(P)}{n\_r}\). The proof combines a reflex-vertex covering property, an averaging argument over individual visibility areas, and a segment construction that preserves or strictly improves the visible area. This yields a constructive, triangulation-free reflex-vertex scanning algorithm. In its basic form, the method scans all reflex vertices, evaluates their visibility areas, selects the best one, and constructs a guaranteed segment; in the strengthened case, the segment is chosen using the first bend of a shortest path from the maximizing reflex vertex to a point outside its visibility region. We also discuss a pairwise refinement over reflex-vertex pairs and state the running time so as to distinguish the combinatorial scan from the geometric cost of evaluating a single visibility candidate.

References

  1. Danny Z. Chen and Haitao Wang. “Weak visibility queries of line segments in simple polygons”. In: Computational Geometry 48.8 (2015), pp. 647–667. DOI: 10.1016/j.comgeo.2015.02.001.
  2. Wei-pang Chin and Simeon Ntafos. “Optimum watchman routes”. In: Information Processing Letters 28.1 (1988), pp. 39–44. DOI: 10.1016/0020-0190(88)90141-X.
  3. W.-P. Chin and S. Ntafos. “Shortest watchman routes in simple polygons”. In: Discrete & Computational Geometry 6.1 (1991), pp. 9–31. DOI : 10.1007/BF02574671.
  4. Svante Carlsson, Håkan Jonsson, and Bengt J. Nilsson. “Finding the shortest watchman route in a simple polygon”. In: Discrete & Computational Geometry 22.3 (1999), pp. 377–402. DOI: 10.1007/PL00009467.
  5. Kien C. Huynh, Joseph S. B. Mitchell, Linh Nguyen, and Valentin Polishchuk. “Optimizing Visibility-Based Search in Polygonal Domains”. In: 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Vol. 294. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024, 27:1–27:16. DOI : 10.4230/LIPIcs.SWAT.2024.27.
  6. Lubomír Štěpánek. “Improved upper bounds on the shortest watchman route in simple polygons: Dependence on reflex vertices and triangulation strategies”. In: Proceedings of the 20th Conference on Computer Science and Intelligence Systems. Vol. 43. Annals of Computer Science and Information Systems. 2025, pp. 789–794. DOI: 10.15439/2025F4752.
  7. B. Joe and R. B. Simpson. “Corrections to Lee’s visibility polygon algorithm”. In: BIT 27 (1987), pp. 458–473. DOI: 10.1007/BF01937271.
  8. Laxmi P. Gewali, Simeon C. Ntafos, and Jörg-Rüdiger Sack. “Placing guards inside orthogonal polygons”. In: Information Sciences 88.1–4 (1996), pp. 1–14. DOI: 10.1016/0020-0255(95)00052-6.
  9. Anna Lubiw and Anurag Murty Naredla. “The Visibility Center of a Simple Polygon”. In: 29th Annual European Symposium on Algorithms (ESA 2021). Vol. 204. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021, 65:1–65:14. DOI : 10.4230/LIPIcs.ESA.2021.65.
  10. Jonathan Richard Shewchuk. “Adaptive precision floating-point arithmetic and fast robust geometric predicates”. In: Discrete & Computational Geometry 18.3 (1997), pp. 305–363. DOI: 10.1007/PL00009321.
  11. Lubomír Štěpánek, Filip Habarta, Ivana Malá, and Luboš Marek. “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”. In: Proceedings of the 18th Conference on Computer Science and Intelligence Systems. Vol. 35. Annals of Computer Science and Information Systems. 2023, pp. 1229–1233. DOI : 10.15439/2023F4335.
  12. Lubomír Štěpánek, Filip Habarta, Ivana Malá, and Luboš Marek. “A Proportion of Visibility Polygon’s Surface to the Entire Polygon’s Surface: A Lower Bound of the Proportion Derived for General Polygons of Any Shape and Orthogonal Polygons”. In: Recent Advances in Computational Optimization. Studies in Computational Intelligence. Cham: Springer Nature Switzerland, 2025, pp. 73–98. DOI : 10.1007/978-3-031-74758-8_4.
  13. Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars. Computational Geometry: Algorithms and Applications. 3rd ed. Berlin, Heidelberg: Springer, 2008. DOI: 10.1007/978-3-540-77974-2.