MAXIMAL AND CONVEX LAYERS OF RANDOM POINT SETS

Abstract

This thesis studies two well-known geometric structures in computational geometry: maximal points and convex hull. Extending the concepts to multiple maximal and convex layers is natural. We study the maximal and convex layers of a point set in $d$ dimensions drawn from a uniform or component-independent (CI) distribution. A distribution is component-independent if each coordinate of a point is chosen independently from a continuous distribution. Precisely, we want to compute and to bound the expected size of the first $k$ layers. For the first set of results, we show that, for $d \in \{2,3\}$, the first $n^{1/d-\epsilon}$ maximal layers can be computed using $dn + o(n)$ scalar comparisons with high probability. For $d \ge 4$, the first $n^{1/2d-\epsilon}$ maximal layers can be computed within this bound with high probability. The first $n^{1/d-\epsilon}$ convex layers in two dimensions, the first $n^{1/2d-\epsilon}$ convex layers in 3D, and the first $n^{1/(d^2+2)}$ convex layers in $d \ge 4$ dimensions can be computed using $2dn + o(n)$ scalar comparisons with high probability. Since the expected number of maximal layers in 2D is $2\sqrt{n}$, our result for 2D maximal layers shows that it takes $dn + o(n)$ scalar comparisons to compute a $1/n^\epsilon$-fraction of all layers in the average case. For the second set of results, we show that the $k$th maximal and convex layer of a point set drawn from a continuous CI distribution in $d$ dimensions has expected size $O(k^d \log^{d-1} (n/k^d))$.