tailieunhanh - The expected number of extreme discs

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. | VNU Journal of Science Mathematics - Physics Vol. 35 No. 2 2019 88-93 Original Article The Expected Number of Extreme Discs Nam-Dung Hoang1 Nguyen Kieu Linh1 2 1Vietnam National University 334 Nguyen Trai Thanh Xuan Hanoi Vietnam 2Posts and Telecommunications institute of Technology Nguyen Trai Ha Dong Hanoi Vietnam Received 12 April 2019 Revised 12 May 2019 Accepted 12 May 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. 1. Introduction Convex hull problem of a finite set of points or discs is one of the most extensively studied and well-understood in computational geometry because of its both theoretical and practical significance. The problem of finding convex hull has been around for about 50 years and its applications have contributed in many different areas such as computer graphics 1 image processing 2 3 and pattern recognition 4 . Besides the convex hull problem is often used as a preprocessing step or as the most important intermediate sub-problem in solving other geometric problems 5 such as Voronoi diagrams constructing triangulation computing the farthest pairs problem 6 . In order to solve the convex hull problem one usually finds the extreme points or discs respectively. In this paper we are interested in the number of extreme discs assuming that the centers of the given discs are randomly distributed. Many algorithms finding the convex hull of a finite set of points have been proposed. It dated back to 1970 for the first publication on convex hull algorithm which was called Gift-wrapping by Chand Corresponding author. Email address .