A new upper bound for the VC-dimension of visibility regions

DOI10.1016/j.comgeo.2013.08.012zbMath1288.65027OpenAlexW2217505494MaRDI QIDQ390367

Rolf Klein, Alexander Gilbers

Publication date: 8 January 2014

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2013.08.012

zbMATH Keywords

VC-dimensionvisibilitycomputational geometryart gallery problemsimple polygonrealizable numbervisibility regionsvisually discernible

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Related Items

Parameterized Analysis of Art Gallery and Terrain Guarding ⋮ The VC dimension of metric balls under Fréchet and Hausdorff distances ⋮ VC-dimension of perimeter visibility domains ⋮ The parameterized complexity of guarding almost convex polygons ⋮ Unnamed Item ⋮ An \(O(\lg \lg {\mathrm {OPT}})\)-approximation algorithm for multi-guarding galleries

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved approximation for guarding simple galleries from the perimeter
• Almost tight bounds for \(\epsilon\)-nets
• Guarding galleries where no point sees a small area.
• Guarding galleries where every point sees a large area
• New Results on Visibility in Simple Polygons
• Small-Size $\eps$-Nets for Axis-Parallel Rectangles and Boxes
• A new upper bound for the VC-dimension of visibility regions
• Visibility Algorithms in the Plane