License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2021.5
URN: urn:nbn:de:0030-drops-154386
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15438/
Gibson-Lopez, Matt ;
Yang, Zhongxiu
The VC-Dimension of Limited Visibility Terrains
Abstract
Visibility problems are fundamental to computational geometry, and many versions of geometric set cover where coverage is based on visibility have been considered. In most settings, points can see "infinitely far" so long as visibility is not "blocked" by some obstacle. In many applications, this may be an unreasonable assumption. In this paper, we consider a new model of visibility where no point can see any other point beyond a sight radius ρ. In particular, we consider this visibility model in the context of terrains. We show that the VC-dimension of limited visibility terrains is exactly 7. We give lower bound construction that shatters a set of 7 points, and we prove that shattering 8 points is not possible.
BibTeX - Entry
@InProceedings{gibsonlopez_et_al:LIPIcs.ISAAC.2021.5,
author = {Gibson-Lopez, Matt and Yang, Zhongxiu},
title = {{The VC-Dimension of Limited Visibility Terrains}},
booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
pages = {5:1--5:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-214-3},
ISSN = {1868-8969},
year = {2021},
volume = {212},
editor = {Ahn, Hee-Kap and Sadakane, Kunihiko},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/15438},
URN = {urn:nbn:de:0030-drops-154386},
doi = {10.4230/LIPIcs.ISAAC.2021.5},
annote = {Keywords: VC-dimension, Terrain Guarding, Limited Visibility}
}
