Local Complexity of Polygons

Abstract

Many problems in Discrete and Computational Geometry deal with simple polygons or polygonal regions. Many algorithms and data-structures perform considerably faster, if the underlying polygonal region has low local complexity. One obstacle to make this intuition rigorous, is the lack of a formal definition of local complexity. Here, we give two possible definitions and show how they are related in a combinatorial sense. We say that a polygon P has point visibility width w=pvw, if there is no point q∈P that sees more than w reflex vertices. We say that a polygon P has chord visibility width w=cvw, if there is no chord c=seg(a,b)⊂P that sees more than w reflex vertices. We show that cvw≤pvwO(pvw), for any simple polygon. Furthermore, we show that there exists a simple polygon with cvw≥2Ω(pvw).