A triangulation-free guard bound for polygonal domains with holes: Structural guarding by outer reflex and hole vertices
Lubomír Štěpánek
DOI: http://dx.doi.org/10.15439/2026F2906
Citation: Lubomír Štěpánek (2026). A triangulation-free guard bound for polygonal domains with holes: Structural guarding by outer reflex and hole vertices. In M. Bolanowski, M. Ganzha, M. Grzegorowski, L. Maciaszek, M. Paprzycki, A. Paszkiewicz, D. Ślęzak (eds), Proceedings of the 21st Conference on Computer Science and Intelligence Systems (FedCSIS). ACSIS, Vol. 47, pages 627–632.
Abstract. We study point guarding of polygonal domains with holes, a classical visibility problem in computational geometry. The goal is to place guards so that every point of the domain is visible from at least one guard. We consider a guard set defined directly by the boundary structure of the domain: all reflex vertices of the outer boundary together with all vertices of the holes. We prove that this guard set always covers the entire domain, including the hole boundaries. The proof is based on Euclidean shortest paths and avoids triangulation. In this way, the result provides a simple structural guarding rule that differs from classical triangulation-based constructions. Classical bounds for polygons with holes are usually stated in terms of the total number of vertices and the number of holes. Our bound is of a different type: it is parameterized by the number of outer-boundary reflex vertices and the total number of hole vertices, rather than relying on a triangulation-based construction. Although it is not uniformly smaller than the classical bounds, it can be substantially better for domains with few outer reflex vertices or with holes of low total boundary complexity. We also show that the dependence on the number of outer reflex vertices is already tight for suitable families of simple polygons.