VC-Dimension of Visibility on Terrains
James A. King · 2008
A guarding problem can naturally be modeled as a set system (U, S) in which the universe U of elements is the set of points we need to guard and our collection S of sets contains, for each potential guard g, the set of points from U seen by g. We prove bounds on the maximum VC-dimension of set systems associated with guarding both 1.5D terrains (monotone chains) and 2.5D terrains (polygonal terrains). We prove that for monotone chains, the maximum VC-dimension is 4 and that for polygonal terrains, the maximum VC-dimension is unbounded. 1