Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
415252 | Computational Geometry | 2014 | 24 Pages |
Abstract
We extend the (recently introduced) notion of k-convexity of a two-dimensional subset of the Euclidean plane to finite point sets. A set of n points is considered k-convex if there exists a spanning (simple) polygonization such that the intersection of any straight line with its interior consists of at most k disjoint intervals. As the main combinatorial result, we show that every n -point set contains a subset of Ω(log2n) points that are in 2-convex position. This bound is asymptotically tight. From an algorithmic point of view, we show that 2-convexity of a finite point set can be decided in polynomial time, whereas the corresponding problem on k -convexity becomes NP-complete for any fixed k≥3k≥3.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Oswin Aichholzer, Franz Aurenhammer, Thomas Hackl, Ferran Hurtado, Alexander Pilz, Pedro Ramos, Jorge Urrutia, Pavel Valtr, Birgit Vogtenhuber,