Path: utzoo!mnetor!uunet!husc6!think!ames!eos!jbm
From: jbm@eos.UUCP (Jeffrey Mulligan)
Newsgroups: comp.graphics
Subject: Re: Algorithm wanted: Circle enclosing points
Message-ID: <494@eos.UUCP>
Date: 4 Apr 88 20:26:35 GMT
References: <496@etn-rad.UUCP>
Organization: NASA Ames Research Center, California
Lines: 32

In article <wWIfSMy00Xo3A5u1dC@andrew.cmu.edu> mp1u+@andrew.cmu.edu (Michael Portuesi) writes:
>I am looking for an efficient algorithm that, given a set of points, finds the
>smallest circle enclosing them and its center.  Pseudocode, actual code (C,

A number of people have proposed solutions involving picking a center,
(by averaging?) and then getting the radius as the distance to the
most distant point.  A key observation is that for the *smallest* circle,
there will be three points which lie on the circle.  Think about it:
if the circle encloses all the points and only contains two of the points,
then you can shrink the radius (while staying on the two points) until
the circle contains another point.  This suggests an algorithm which,
although expensive (especially for large N), is guaranteed to give the
correct solution:

1)  Make a list of all triples of points (there are N choose 3 of them).

2)  Treating each triple of points as the vertices of a triangle,
	compute the radius of the circumscribing circle.

3)  The largest circumcircle is the desired result.

There are probably ways to get tricky and speed this up;  for example,
if a point can be determined to lie within a triangle already on the list
(in step 1) then all triangles containing that point can be discarded.
It is unclear whether the cost of this test will be less than the cost
of computing some extra circumcircles.

-- 

	Jeff Mulligan (jbm@ames-aurora.arpa)
	NASA/Ames Research Ctr., Mail Stop 239-3, Moffet Field CA, 94035
	(415) 694-5150