Counting the onion

Autor: Ketan Dalal
Rok vydání: 2004
Předmět:
Zdroj: Random Structures and Algorithms. 24:155-165
ISSN: 1098-2418
1042-9832
DOI: 10.1002/rsa.10114
Popis: 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 Θ(n2/3). Additionally, we show that in general the bound is Θ(n2/(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.
Databáze: OpenAIRE