Path: utzoo!mnetor!uunet!husc6!bbn!rochester!cornell!batcomputer!sun.soe.clarkson.edu!naughton
From: naughton@sun.soe.clarkson.edu (Patrick Naughton)
Newsgroups: comp.graphics
Subject: Re: Algorithm wanted: Circle enclosing points
Message-ID: <682@sun.soe.clarkson.edu>
Date: 4 Apr 88 23:20:13 GMT
References: <494@eos.UUCP>
Organization: Clarkson University, Potsdam, NY
Lines: 41

From article <494@eos.UUCP>, by jbm@eos.UUCP (Jeffrey Mulligan):
> 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:

It may be "A key observation",  but it is an incorrect one.

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

Again, this fails to find the *smallest* circle that encloses the points...

Picture three points arranged in a straight line.

The algorithm above would tell us that a circle of infinite radius is the
smallest possible circle which will enclose these three points.

Sorry for giving nothing but negative replies here but, I don't know the
solution and would like to see something other than off the cuff guesses.

-Patrick	 ___________________________________________
		|                                           |
		|  Internet: naughton@sun.soe.clarkson.edu  |
		|  BITNET:   naughton@CLUTX.BITNET          |
		|  uucp:     {rpics, gould}!clutx!naughton  |
		|___________________________________________|