On $k$-convex polygons

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

Abstract:

We introduce the notion of $k$-convexity and explore polygons in the plane that have this property. Polygons which are $k$-convex can be triangulated with fast yet simple algorithms. However, recognizing them is a 3SUM-hard problem. We give a characterization of 2-convex polygons, a particularly interesting class, and show how to recognize them in $O(n \log n)$ time. A description of their shape is given as well, which leads to Erdos-Szekeres type results regarding subconfigurations of their vertex sets. Finally, we introduce the concept of generalized geometric permutations, and show that their number can be exponential in the number of 2-convex objects considered.

Reference: O. Aichholzer, F. Aurenhammer, E. Demaine, F. Hurtado, P. Ramos, and J. Urrutia. On $k$-convex polygons. Computational Geometry: Theory and Applications, 45(3):73-87, 2012.