Exact VC-dimension for L₁-visibility of points in simple polygons

2017/05/04 by Langetepe, Elmar, Lehmann, Simone
#Computational Geometry (cs.CG) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1705.01723

Abstract

The VC-dimension plays an important role for the algorithmic problem of guarding art galleries efficiently. We prove that inside a simple polygon at most 5 points can be shattered by L₁-visibility polygons and give an example where 5 points are shattered. The VC-dimension is exactly 5. The proof idea for the upper bound is different from previous approaches. Keywords: Art gallery, VC-dimension, L₁-visibility, polygons

Related

• A New Upper Bound for the VC-Dimension of Visibility Regions
• Implementation of polygon guarding algorithms for art gallery problems
• A note on minimal art galleries
• Visibility Extension via Reflection
• On the Complexity of Half-Guarding Monotone Polygons