[HTML][HTML] The VC-dimension of visibility on the boundary of monotone polygons

M Gibson, E Krohn, Q Wang - Computational Geometry, 2019 - Elsevier
M Gibson, E Krohn, Q Wang
Computational Geometry, 2019Elsevier
… Note that our lower bound result matches the current lower bound result for simple
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
monotone polygons 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.
Elsevier
以上显示的是最相近的搜索结果。 查看全部搜索结果