The Expected Number of Extreme Discs
Nam-Dũng Hoàng, Nguyen Kieu Linh · VNU Journal of Science Mathematics - Physics · 2019
Abstract: Given a finite set D of n planar discs whose centers are distributed randomly. We are interested in the expected number of extreme discs of the convex hull of D. We show that the expected number of extreme discs is at most O(log2n) for any distribution. This result can be used to derive expected complexity of convex hull algorithms. Keywords: Convex hull, computational geometry, expected number. Mathematics Subject Classification (2010): 65D18, 52A15, 51N05.