Expected Size of Random Tukey Layers and Convex Layers

Abstract

We study the Tukey layers and convex layers of a planar point set, which consists of $n$ points independently and uniformly sampled from a convex polygon with $k$ vertices. We show that the expected number of vertices on the first $t$ Tukey layers is $O\left(kt\log (n/k)\right)$ and the expected number of vertices on the first $t$ convex layers is $O\left(k{t}^3\log (n/(k{t}^2))\right)$. We also show a lower bound of $\Omega (t\log n)$ for both quantities in the special cases where $k=3,4$. The implications of those results in the average-case analysis of two computational geometry algorithms are then discussed.

References in corpus (1)

• Minimum Enclosing Parallelogram with Outliers