From: Rasmus Pagh
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 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.
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.
<