Counting the onion

Iteratively computing and discarding a set of convex hulls creates a structure known as an “onion.” In this paper, we show that the expected number of layers of a convex hull onion for n uniformly and independently distributed points in a disk is Θ(n^2/3). Additionally, we show that in general the bound is Θ(n^2/(d+1)) for points distributed in a d‐dimensional ball. Further, we show that this bound holds more generally for any fixed, bounded, full‐dimensional shape with a nonempty interior. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004