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 |
Externí odkaz: |