Large convex holes in random point sets
| Autor: | Balogh, József, González-Aguilar, Hernán, Salazar, Gelasio |
|---|---|
| Rok vydání: | 2012 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | A {\em convex hole} (or {\em empty convex polygon)} of a point set $P$ in the plane is a convex polygon with vertices in $P$, containing no points of $P$ in its interior. Let $R$ be a bounded convex region in the plane. We show that the expected number of vertices of the largest convex hole of a set of $n$ random points chosen independently and uniformly over $R$ is $\Theta(\log{n}/(\log{\log{n}}))$, regardless of the shape of $R$. |
| Databáze: | arXiv |
| Externí odkaz: |
|