Two-Convex Polygons

O. Aichholzer, F. Aurenhammer, F. Hurtado, P. Ramos, and J. Urrutia

Abstract:

We introduce a notion of $k$-convexity and explore some properties of polygons that have this property. In particular, $2$-convex polygons can be recognized in $O(n \log n)$ time, and $k$-convex polygons can be triangulated in $O(kn)$ time.

Reference: O. Aichholzer, F. Aurenhammer, F. Hurtado, P. Ramos, and J. Urrutia. Two-convex polygons. In Proc. $25^{th}$ European Workshop on Computational Geometry EuroCG '09, pages 117-120, Brussels, Belgium, 2009.