polygons. Valtr's lower bound construction does not place all of the viewpoints on the boundary of the polygon, and therefore our result improves the best known lower bound for the VC-dimension of visibility in the boundary of simple polygons as well. Given that monotonepolygons are seemingly quite restrictive relative to general simple polygons, we find our lower bound to be a somewhat surprising result. …
Abstract
We show that the VC-dimension of visibility on the boundary of a monotone polygon is exactly 6. Our lower bound construction matches the best known lower bound for simple polygons.