From: eppstein@euclid.ics.uci.edu (David Eppstein)
Newsgroups: sci.math
Subject: Re: How to find the minimum circumscribed circle of a 5-D ploygon
Date: 16 Oct 1997 10:50:45 -0700

Reine Lindqvist <reine@na.chalmers.se> writes:
> I'm looking for  an algorithm (MATLAB, FORTRAN, C++) for finding the
> minimum circumscribed hypersphere to a curve Q of a 5th-dimensional
> space approximated by a set P of m points (a 5-D polygon)..

There are several publically available implementations at
http://www.geom.umn.edu/software/cglist/lp.html
-- 
David Eppstein		UC Irvine Dept. of Information & Computer Science
eppstein@ics.uci.edu	http://www.ics.uci.edu/~eppstein/
==============================================================================

From: Jeff Erickson <jeffe@sal.cs.uiuc.edu>
Newsgroups: sci.math.research
Subject: Re: Smallest circle enclosing a set of points
Date: Mon, 24 Aug 1998 19:56:11 -0500

tchow[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