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