| Autor: |
Aichholzer, Oswin, Fabila-Monroy, Ruy, González-Aguilar, Hernán, Hackl, Thomas, Heredia, Marco A., Huemer, Clemens, Urrutia, Jorge, Valtr, Pavel, Vogtenhuber, Birgit |
| Rok vydání: |
2014 |
| Předmět: |
|
| Druh dokumentu: |
Working Paper |
| Popis: |
We consider a variation of the classical Erd\H{o}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. |
| Databáze: |
arXiv |
| Externí odkaz: |
|
