2024/06/09 by Sándor P. Fekete, Joseph S. B. Mitchell, Fekete, Sándor P. +7 · 1 citation
Computer Science · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #F.2.2 #FOS: Computer and information sciences #Handwritten Text Recognition Techniques #Image Processing and 3D Reconstruction
paper · pdf · doi:10.48550/arxiv.2406.05861
openalex publication_date 2024/06/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the Dispersive Art Gallery Problem with vertex guards: Given a polygon P, with pairwise geodesic Euclidean vertex distance of at least 1, and a rational number ℓ; decide whether there is a set of vertex guards such that P is guarded, and the minimum geodesic Euclidean distance between any two guards (the so-called dispersion distance) is at least ℓ. We show that it is NP-complete to decide whether a polygon with holes has a set of vertex guards with dispersion distance 2. On the other hand, we provide an algorithm that places vertex guards in simple polygons at dispersion distance at least 2. This result is tight, as there are simple polygons in which any vertex guard set has a dispersion distance of at most 2.