The VC-dimension of visibility on the boundary of monotone polygons

摘要

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. (C) 2018 Published by Elsevier B.V.