2012/06/25 by Alexander Gilbers, Gilbers, Alexander, Rolf Klein +1 · 1 citation
Computer Science · Engineering · #Advanced Numerical Analysis Techniques #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #F.2.2 #FOS: Computer and information sciences #Robotic Path Planning Algorithms #cs.CG
paper · pdf · doi:10.48550/arxiv.1206.5689
25 pages, 18 Figures. An extended abstract of this paper appeared at SoCG '11
arxiv created 2012/06/25 · openalex publication_date 2012/06/25 · arxiv updated 2012/06/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we are proving the following fact. Let P be an arbitrary simple polygon, and let S be an arbitrary set of 15 points inside P. Then there exists a subset T of S that is not "visually discernible", that is, T is not equal to the intersection of S with the visibility region vis(v) of any point v in P. In other words, the VC-dimension d of visibility regions in a simple polygon cannot exceed 14. Since Valtr proved in 1998 that d ∈ [6,23] holds, no progress has been made on this bound. By epsilon-net theorems our reduction immediately implies a smaller upper bound to the number of guards needed to cover P.