Abstract
A simple randomized algorithm is developed which computes the smallest enclosing disk of a finite set of points in the plane in expected linear time. The algorithm is based on Seidel's recent Linear Programming algorithm, and it can be generalized to computing smallest enclosing balls or ellipsoids of point sets in higher dimensions in a straightforward way. Experimental results of an implementation are presented.
Work partially supported by the ESPRIT II Basic Research Action Program of the EC under contract no. 3075 (project ALCOM)
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
V. Barnett, The ordering of multivariate data, J.Roy.Statist. Soc. Ser. A 139 (176) 318–354
F. Behrend, Über die kleinste umbeschriebene und die größte einbeschriebene Ellipse eines konvexen Bereiches, Math. Ann. 115 (1938) 379–411
K. L. Clarkson, Las Vegas algorithms for linear and integer programming when the dimension is small, manuscript (1989)
L. Danzer, D. Laugwitz and H. Lenz, Über das Löwnersche Ellipsoid und sein Analogon unter den einem Eikörper eingeschriebenen Ellipsoiden, Arch. Math. 8 (1957) 214–219
M. E. Dyer and A. M. Frieze, A randomized algorithm for fixed-dimensional linear programming, manuscript (1987)
J. Dörflinger and W. Forst, Approximation durch Kreise: Verfahren zur Berechnung der Hüllkugel, manuscript (1991)
F. John, Extremum problems with inequalities as subsidiary conditions, in Courant Anniversary Volume (1948) 187–204, New York
F. Juhnke, Löwner ellipsoids via semiinfinite optimization and (quasi-) convexity theory, Technische Universität Magdeburg, Sektion Mathematik, Report 4/90 (1990)
H. Jung, Über die kleinste Kugel, die eine räumliche Figur einschließt, J. Reine Angew. Math. 123 (1901) 241–257
K. Leichtweiß, Über die affine Exzentrizität konvexer Körper, Arch. Math. 10 (1959) 187–199
N. Megiddo, Linear-time algorithms for linear programming in ℝ3 and related problems, SIAM J. Comput. 12 (1983) 759–776
M. J. Post, Minimum spanning ellipsoids, in “Proc. 16th Annual ACM Symposium on Theory of Computing” (1984) 108–116
R. Seidel, Linear programming and convex hulls made easy, in “Proc. 6th Annual ACM Symposium on Computational Geometry” (1990) 211–215
R. Seidel, Backwards analysis of randomized algorithms, manuscript (1991)
B. W. Silverman and D. M. Titterington, Minimum covering ellipses, SIAM J. Sci. Slat. Comput. 1 (1980) 401–409
M. Shark and E. Welzl, A new combinatorial bound for linear programming and related problems, in preparation (1991)
S. Skyum, A simple algorithm for computing the smallest circle, Aarhus University, Report DAIMI PB-314
D. M. Titterington, Estimation of correlation coefficients by ellipsoidal trimming, Appl. Statist. 27 (1978) 227–234
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1991 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Welzl, E. (1991). Smallest enclosing disks (balls and ellipsoids). In: Maurer, H. (eds) New Results and New Trends in Computer Science. Lecture Notes in Computer Science, vol 555. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0038202
Download citation
DOI: https://doi.org/10.1007/BFb0038202
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-54869-0
Online ISBN: 978-3-540-46457-0
eBook Packages: Springer Book Archive