Abstract | ||
---|---|---|
We consider a variation of the classical Erdős–Szekeres problems on the existence and number of convex k-gons and k-holes (empty k-gons) in a set of n points in the plane. Allowing the k-gons to be non-convex, we show bounds and structural results on maximizing and minimizing their numbers. Most noteworthy, for any k and sufficiently large n, we give a quadratic lower bound for the number of k-holes, and show that this number is maximized by sets in convex position. |
Year | DOI | Venue |
---|---|---|
2014 | 10.1016/j.comgeo.2014.12.007 | Computational Geometry |
Keywords | Field | DocType |
Erdős–Szekeres type problems,k-Gons,k-Holes,Empty k-gons | Discrete mathematics,Combinatorics,Upper and lower bounds,Quadratic equation,Regular polygon,Convex position,Mathematics | Journal |
Volume | Issue | ISSN |
48 | 7 | 0925-7721 |
Citations | PageRank | References |
7 | 0.90 | 19 |
Authors | ||
9 |
Name | Order | Citations | PageRank |
---|---|---|---|
Oswin Aichholzer | 1 | 852 | 96.04 |
Ruy Fabila Monroy | 2 | 48 | 16.57 |
HernáN GonzáLez-Aguilar | 3 | 19 | 4.23 |
Thomas Hackl | 4 | 138 | 22.95 |
Marco A. Heredia | 5 | 17 | 3.65 |
Clemens Huemer | 6 | 167 | 24.93 |
Jorge Urrutia | 7 | 1064 | 134.74 |
Pavel Valtr | 8 | 397 | 77.30 |
Birgit Vogtenhuber | 9 | 127 | 27.19 |