The Expected Number of Extreme Discs - Hoang, Nam-Dung; Linh, Nguyen Kieu (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(log 2 n ) 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. References [1] P. Bhaniramka, R. Wenger, R. Crawfis, Isosurface construction in any dimension using convex hulls, IEEE Transactions on Visualization and Computer Graphics 10 (2004) 130-141. [2] M. Nikolay, Sirakov et al., Search space partitioning using convex hull and concavity features for fast medical image retrieval, in: Proc. of the IEEE International Symposium on Biomedical Imaging, Arlington, USA (2004) 796-799. [3] B. Yuan, C.L. Tan, Convex hull based skew estimation, Pattern Recognition 40 (2007) 456-475. [4] S.G. Akl, G.T. Toussaint, Efficient convex hull algorithms for pattern recognition applications, Int. Joint Conf. on Pattern Recognition, Kyoto, Japan, (1978) 483-487. [5] J. O’Rourke, Computational geometry in C, 2nd edition, Cambridge University Press, Cambridge, 1998. [6] R. Suneeta, Convex Hulls: Complexity and applications (A Survey), University of Pennsylvania, 1993. [7] D.R. Chand, S. S. Kapur, An algorithm for convex polytopes, Journal of the ACM 1 (1970) 78-86. [8] R.L. Graham, An efficient algorithm for determining the convex hull of a finite planar set, Information Processing Letters 1 (1972) 132-133. [9] A. Bykat, Convex hull of a finite set of points in two dimensions, Information Processing Letters 7 (1978) 296-298. [10] M. Kallay, The complexity of incremental convex hull algorithms in Information Processing Letters 19 (1984) 197. [11] D.G. Kirkpatrick, R. Seidel, The ultimate planar convex hull algorithm? SIAM Journal on Computing 15 (1986) 287-299. [12] T.M. Chan, Optimal output-sensitive convex hull algorithms in two and three dimensions, Discrete & Computational Geometry 16 (1996) 361-368. [13] 7-V. Damerow, C. Sohler, Extreme points under random noise, European Symposium on Algorithms 3221 (2004) 264-274. [14] D. Rappaport, A convex hull algorithm for discs, and application, Computational Geometry: Theory and Applications 1 (1992) 171-187. [15] O. Devillers, M.J. Golin, Incremental algorithm for finding the convex hulls of discs and the lower envelopes of parabolas", Information Processing Letters 56 (1995) 157-164. [16] W. Chen, K. Wada, K. Kawaguchi, D.Z. Chen, Finding the convex hull of discs in parallel, International Journal of Computational Geometry & Applications 3 (1998) 305-319. [17] N.K. Linh, Bài toán tìm bao lồi của tập hữu hạn các điểm hoặc các hình tròn, Đại học Khoa học Tự Nhiên, Đại học Quốc gia Hà Nội, 2019. [18] F.P. Preparata, M.I. Shamos, Computational geometry, 2nd Printing. Springer Verlag, New York, 1985. [19] W.F. Eddy, A new convex hull algorithm for planar sets, ACM Transactions on Mathematical Software: ACM TOMS (1977) 398-403.