Premium
Counting the onion
Author(s) -
Dalal Ketan
Publication year - 2004
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.10114
Subject(s) - convex hull , regular polygon , bounded function , combinatorics , mathematics , upper and lower bounds , ball (mathematics) , hull , convex body , set (abstract data type) , discrete mathematics , geometry , computer science , mathematical analysis , engineering , marine engineering , programming language
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