On k-Convex Polygons

Details On k-Convex Polygons On k-Convex Polygons

2010-07-21

arxiv.org/abs/1007.3607v1

Computer Science

Computational Geometry

23 pages, 19 figures

Scientific paper

We introduce a notion of $k$-convexity and explore polygons in the plane that have this property. Polygons which are \mbox{$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 \mbox{$2$-convex} polygons, a particularly interesting class, and show how to recognize them in \mbox{$O(n \log n)$} time. A description of their shape is given as well, which leads to Erd\H{o}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 \mbox{$2$-convex} objects considered.

Affiliated with

Also associated with

No associations

Rating

On k-Convex Polygons does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On k-Convex Polygons, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On k-Convex Polygons will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-183588