Geometric Algorithms for Minimal Enclosing Disks in Strictly Convex Normed Planes


  • Thomas Jahn Technische Universität Chemnitz



minimal enclosing disk, norm-acute triangle, norm-obtuse triangle, strictly convex normed space, Voronoi diagram


With the geometric background provided by Alonso, Martini, and Spirova
on the location of circumcenters of triangles in normed planes, we show the validity of the Elzinga--Hearn algorithm and the Shamos--Hoey algorithm for solving the minimal enclosing disk problem in strictly convex normed planes.


J. Alonso, H. Martini, and M. Spirova, Minimal enclosing discs, circumcircles, and circumcenters in normed planes (Part I), Comput. Geom. 45 (2012), no. 5-6, pp. 258--274,

J. Alonso, H. Martini, and M. Spirova, Minimal enclosing discs, circumcircles, and circumcenters in normed planes (Part II), Comput. Geom. 45 (2012), no. 7, pp. 350--369,

D. Amir and Z. Ziegler, Relative Chebyshev centers in normed linear spaces, Part I, J. Approx. Theory 29 (1980), no. 3, pp. 235--252,

B. Chazelle and H. Edelsbrunner, An improved algorithm for constructing $k$th-order Voronoi diagrams, IEEE Trans. Comput. C-36 (1987), no. 11, pp 1349--1354,

L. P. Chew and R. L. S. Drysdale, Voronoi diagrams based on convex distance functions, Proceedings of the First Annual Symposium on Computational Geometry (J. O'Rourke, ed.), ACM, 1985, pp. 235--244,

G. Chrystal, On the problem to construct the minimum circle enclosing $n$ given points in a plane, Proc. Edinburgh Math. Soc. 3 (1885), pp. 30--33.

Z. Drezner and S. Shelah, On the complexity of the Elzinga--Hearn algorithm for the $1$-center problem, Math. Oper. Res. 12 (1987), no. 2, pp. 255--261,

J. Elzinga and D. W. Hearn, Geometrical solutions for some minimax location problems, Transportation Sci. 6 (1972), no. 4, pp. 379--394,

P. Gritzmann and V. Klee, Inner and outer $j$-radii of convex bodies in finite-dimensional normed spaces, Discrete Comput. Geom. 7 (1992), no. 1, pp. 255--280,

D. T. Lee, Two-dimensional Voronoi diagrams in the $L_p$-metric}, J. Assoc. Comput. Mach. 27 (1980), no. 4, pp. 604--618,

D. T. Lee, On $k$-nearest neighbor Voronoi diagrams in the plane, IEEE Trans. Comput. 31 (1982), no. 6, pp. 478--487,

L. Ma, Bisectors and Voronoi Diagrams for Convex Distance Functions, PhD thesis, Fernuniversität Hagen, 2000.

H. Martini, K. Swanepoel, and G. Wei{\ss}, The geometry of Minkowski spaces -- a survey, Part I, Expo. Math. 19 (2001), no. 2, pp. 97--142,

N. Megiddo, Linear-time algorithms for linear programming in $\mathds{R}^3$ and related problems, SIAM J. Comput. 12 (1983), no. 4, pp. 759--776,

H. Rademacher and O. Toeplitz, The Enjoyment of Math, 7th ed., Princeton University Press, Princeton, 1994.

M. I. Shamos and D. Hoey, Closest-point problems, 16th Annual Symposium on Foundations of Computer Science (Berkeley, Calif., 1975), IEEE Comput. Soc., 1975, pp. 151--162,

J. J. Sylvester, A question in the geometry of situation, Q. J. Math. 1 (1857), p. 79.

J. Väisälä, Slopes of bisectors in normed planes, Beitr. Algebra Geom. 54 (2013), no. 1, pp. 225--235,

E.~Welzl, Smallest enclosing discs (balls and ellipsoids), New Results and New Trends in Computer Science (H.~Maurer, ed.), Lecture Notes in Computer Science, vol. 555, Springer, Berlin, 1991, pp. 359--370,