A new upper bound for the VC-dimension of visibility regions (Q390367): Difference between revisions

The paper is focused on the visibility problem related to the art gallery problem. For a given simple polygon and a finite set of points inside this polygon, the authors show that the biggest realizable number -- so-called VC-dimension of visibility regions in simple polygons -- is less or equal to 14. This conclusion disproves the previously known upper bound 23. Assuming a simple polygon containing a set of 15 points each of whose subsets is visually discernible, the authors firstly show that at most 5 points can be situated inside the convex hull of the 15 points set. Secondly, the authors prove that at most 9 points can be located on the convex hull.