On k-Convex Polygons

2010/07/21 by Aichholzer, Oswin, Aurenhammer, Franz, Demaine, Erik D. +3
#Combinatorics (math.CO) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1007.3607

Abstract

We introduce a 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 in general 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 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.

Related

• Triangulations of nearly convex polygons
• On the representation of finite convex geometries with convex sets
• Families of m-convex polygons: m = 2
• Which convex polyhedra can be made by gluing regular hexagons?
• Counting Triangulations of Configurations