On -convex polygons
O. Aichholzer, F. Aurenhammer, E. Demaine, F. Hurtado, P. Ramos, and
We introduce the notion of
-convexity and explore polygons in the plane that
have this property. Polygons which are
-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
time. A description of
their shape is given as well, which leads to Erdös-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 -convex polygons.
Computational Geometry: Theory and Applications, 45:73-87, 2012.