The Expected Number of Extreme Discs
Main Article Content
Abstract
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.
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.
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.