Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Gibson-Lopez, Matt; Yang, Zhongxiu https://www.dagstuhl.de/lipics License: Creative Commons Attribution 4.0 license (CC BY 4.0)
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-154386
URL:

;

The VC-Dimension of Limited Visibility Terrains

pdf-format:


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}
}

Keywords: VC-dimension, Terrain Guarding, Limited Visibility
Seminar: 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Issue date: 2021
Date of publication: 30.11.2021
Supplementary Material: Software (Source Code for Lower Bound): https://github.com/utsa-saga/vc7proof archived at: https://archive.softwareheritage.org/swh:1:dir:33dfe57e9e3cb7a1fad1a49f6bd65a0fa1e32a67
Software (Source Code for Upper Bound): https://github.com/utsa-saga/vc8proof archived at: https://archive.softwareheritage.org/swh:1:dir:bffd67e203db12523de2cc9f76baa84d3b6046d0


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI