The VC-dimension of visibility on the boundary of monotone polygons

DOI10.1016/j.comgeo.2018.10.006zbMath1506.68173OpenAlexW2898476453WikidataQ129048234 ScholiaQ129048234MaRDI QIDQ1630914

Qing Wang, Matthew R. Gibson, Erik A. Krohn

Publication date: 5 December 2018

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

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

zbMATH Keywords

VC-dimensionvisibilitycomputational geometryart gallery problemmonotone polygons

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• VC-dimension of perimeter visibility domains
• Improved approximation for guarding simple galleries from the perimeter
• Guarding galleries and terrains
• Guarding galleries where no point sees a small area.
• Almost optimal set covers in finite VC-dimension
• Approximate guarding of monotone and rectilinear polygons
• Terrain Guarding is NP-Hard
• A Pseudopolynomial Time O(logn)-Approximation Algorithm for Art Gallery Problems
• An Approximation Scheme for Terrain Guarding
• Computational complexity of art gallery problems
• A new upper bound for the VC-dimension of visibility regions

This page was built for publication: The VC-dimension of visibility on the boundary of monotone polygons