From: Rasmus Pagh <pagh@daimi.au.dk>
Subject: Re: Minimal circum sphere of a discrete set of points?
Date: Mon, 22 Mar 1999 18:06:19 +0100
Newsgroups: sci.math.research,sci.math
Keywords: bounding sphere

Martin Kraus wrote:
> the question arose how to calculate
> the minimal circum sphere of a given discrete set of points.
> we are not aware of any publication about this problem. Does 
> anyone else know something about it?

This is a well studied problem in computational geometry.
There is a simple randomized algorithm which runs in expected 
time O(n) (at least in the planar case), and using linear 
programming techniques one can also obtain efficient 
deterministic algorithms (again O(n) in the planar case).

"Computational Geometry" by M. de Berg et al, provides the 
randomized algorithm mentioned, and further references.

/Rasmus

-- 
_________________________________________________________________

 Rasmus Pagh (pagh@daimi.au.dk)    http://www.daimi.au.dk/~pagh/
_________________________________________________________________
==============================================================================

From: nospam@nospam.mit.edu
Subject: Re: Minimal circum sphere of a discrete set of points?
Date: 22 Mar 1999 20:50:15 -0500
Newsgroups: sci.math.research,sci.math

In article <36F6788B.52EF6D7D@daimi.au.dk>,
Rasmus Pagh  <pagh@daimi.au.dk> wrote:
>Martin Kraus wrote:
>> the question arose how to calculate
>> the minimal circum sphere of a given discrete set of points.
>
>"Computational Geometry" by M. de Berg et al, provides the 
>randomized algorithm mentioned, and further references.

Jeff Erickson gave an excellent response when I posted this question back
in August.


<Subject: Re: Smallest circle enclosing a set of points
<Date: 24 Aug 1998 00:00:00 GMT
<From: Jeff Erickson <jeffe@sal.cs.uiuc.edu>
<Organization: Dept. of Computer Science, Univ. of Illinois, Urbana-Champaign
<Newsgroups: sci.math.research
<
<tchow[email address deleted] wrote:
<
<> Given the coordinates of a finite set of points in the plane, I want
<> an efficient algorithm to find the center and radius of a smallest
<> circle enclosing all the points.
<
<It can be found in linear time using an algorithm of Welzl.  In fact,
<Welzl's algorithm can find the minimum-volume enclosing sphere of any
<set of points in any constant dimension in linear time (although
<"linear" hides a constant that is exponential in the dimension).
<
<@incollection{w-sedbe-91a
<, author =      "Emo Welzl"
<, title =       "Smallest enclosing disks (balls and ellipsoids)"
<, editor =      "H. Maurer"
<, booktitle =   "New Results and New Trends in Computer Science"
<, series =      "Lecture Notes Comput. Sci."
<, volume =      555
<, publisher =   "Springer-Verlag"
<, year =        1991
<, pages =       "359--370"
<}
<
<For more recent (and more general) results, with sub-exponential
<dependence on the dimension, see:
<
<@article{c-lvali-95
<, author =      "K. L. Clarkson"
<, title =       "{Las} {Vegas} algorithms for linear and integer
<                 programming"
<, journal =     "J. ACM"
<, volume =      42
<, year =        1995
<, pages =       "488--499"
<}
<
<@article{msw-sblp-96
<, author =      "J. Matou{\v s}ek and Micha Sharir and Emo Welzl"
<, title =       "A subexponential bound for linear programming"
<, journal =     "Algorithmica"
<, volume =      16
<, year =        1996
<, pages =       "498--516"
<}
<
<Finally, for a working implementation of Welzl's algorithm (which
<actually finds the smallest ball enclosing a set of balls, also in
<linear time), see:
<
<        http://vision.ucsd.edu/~dwhite/ball.html
<
<--
<Jeff Erickson                                        jeffe@cs.uiuc.edu
<Computer Science Department           http://www.uiuc.edu/ph/www/jeffe
<University of Illinois, Urbana-Champaign
-- 
Tim Chow       tchow-at-alum-dot-mit-dot-edu
Where a calculator like the ENIAC today is equipped with 18,000 vacuum tubes
and weighs 30 tons, computers in the future may have only 1,000 vacuum tubes
and perhaps weigh only 1 1/2 tons.   ---Popular Mechanics, March 1949, p.258