Proceedings of the 20th Conference on Computer Science and Intelligence Systems (FedCSIS)

DOI: http://dx.doi.org/10.15439/2025F4752

Citation: Proceedings of the 20th Conference on Computer Science and Intelligence Systems (FedCSIS), M. Bolanowski, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 43, pages 789–794 (2025)

Full text

Abstract. This paper investigates upper bounds on the length of the shortest watchman route in simple polygons using minimal structural information -- specifically, the number and placement of reflex vertices -- rather than full geometric detail. We show that the set of reflex vertices alone suffices to guarantee full visibility of the polygon: every interior or boundary point is visible from at least one reflex vertex. Moreover, these vertices can always be connected by a polyline within the polygon, enabling a constructive approach to route design. While it is known that the shortest watchman route is bounded above by the perimeter of the polygon, we prove that this bound is tight and cannot be improved in general. However, we identify several important classes of polygons where significantly better bounds are achievable. In particular, for polygons with exactly two reflex vertices, we establish that the shortest watchman route is strictly shorter than half the perimeter. We also introduce a novel triangulation method -- successive dual-edge triangulation -- in which each triangle is constructed by attaching to existing polygon edges. When such a triangulation is possible, the resulting watchman route has length strictly less than half the perimeter, regardless of the number of sides or reflex vertices. These results are not only theoretical but also constructive, offering efficient route designs when geometric data is available. The approach is particularly well suited to real-world environments such as industrial halls or private courtyards, where structural simplicity often permits route planning without requiring full geometric reconstruction. In such cases, our methods provide a significant and elegant reduction in route length compared to perimeter-based patrolling, making them applicable to scenarios such as autonomous drone navigation and indoor surveillance.

References

1. S. Carlsson, H. Jonsson, and B. J. Nilsson. “Finding the Shortest Watchman Route in a Simple Polygon”. In: Discrete & Computational Geometry 22.3 (Oct. 1999), pp. 377–402. ISSN: 0179-5376. DOI: 10.1007/pl00009467.
2. X. Tan. “Fast computation of shortest watchman routes in simple polygons”. In: Information Processing Letters 77.1 (Jan. 2001), pp. 27–33. ISSN : 0020-0190. DOI: 10.1016/s0020-0190(00)00146-0.
3. W.-P. Chin and S. Ntafos. “Shortest watchman routes in simple polygons”. In: Discrete & Computational Geometry 6.1 (Mar. 1991), pp. 9–31. ISSN : 1432-0444. DOI : 10.1007/bf02574671.
4. J. S. B. Mitchell. “Approximating Watchman Routes”. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, Jan. 2013, pp. 844–855. DOI: 10.1137/1.9781611973105.60.
5. A. Dumitrescu and C. D. Tóth. “Watchman tours for polygons with holes”. In: Computational Geometry 45.7 (Aug. 2012), pp. 326–333. ISSN: 0925-7721. DOI: 10.1016/j.comgeo.2012. 02.001.
6. J. Faigl. “Approximate Solution of the Multiple Watchman Routes Problem With Restricted Visibility Range”. In: IEEE Transactions on Neural Networks 21.10 (Oct. 2010), pp. 1668–1679. ISSN: 1941-0093. DOI: 10.1109/tnn.2010.2070518.
7. J. Mikula and M. Kulich. “Towards a Continuous Solution of the d-Visibility Watchman Route Problem in a Polygon With Holes”. In: IEEE Robotics and Automation Letters 7.3 (July 2022), pp. 5934–5941. ISSN : 2377-3774. DOI : 10.1109/lra.2022.3159824.
8. B. J. Nilsson and E. Packer. “Approximation Algorithms for the Two-Watchman Route in a Simple Polygon”. In: Algorithmica 86.9 (June 2024), pp. 2845–2884. ISSN: 1432-0541. DOI: 10.1007/s00453-024-01245-0.
9. L. Štěpánek, F. Habarta, I. Malá, and L. 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. FedCSIS 2023. IEEE, Sept. 2023, pp. 1229–1233. DOI: 10.15439/2023f4335.
10. L. Štěpánek, F. Habarta, I. Malá, and L. 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. Springer Nature Switzerland, 2025, pp. 73–98. ISBN: 9783031747588. DOI: 10.1007/978-3-031-74758-8_4.
11. C. Lavor, L. Liberti, N. Maculan, and A. Mucherino. “The discretizable molecular distance geometry problem”. In: Computational Optimization and Applications 52.1 (Mar. 2011), pp. 115–146. ISSN: 1573-2894. DOI: 10.1007/s10589-011-9402-6. URL: http://dx.doi.org/10.1007/s10589-011-9402-6.