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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom