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.