Path: utzoo!mnetor!uunet!husc6!bloom-beacon!mit-eddie!uw-beaver!cornell!batcomputer!garry
From: garry@batcomputer.tn.cornell.edu (Garry Wiegand)
Newsgroups: comp.graphics
Subject: Re: Algorithm wanted: Circle enclosing points
Message-ID: <4306@batcomputer.tn.cornell.edu>
Date: 4 Apr 88 23:39:32 GMT
Reply-To: garry@oak.cadif.cornell.edu
Organization: Cornell Engineering && Ithaca Software, Inc.
Lines: 25

In a recent article jbm@eos.UUCP (Jeffrey Mulligan) wrote:
>...  A key observation is that for the *smallest* circle,
>there will be three points which lie on the circle...

A simple counterexample for you: consider a set of three points 
that lie approximately in a straight line. 

(I'd be willing to postulate that at least *two* points are on the
 edge, assuming the point set is not degenerate.)

---
Exhaustive search for this problem is probably O(n^3). I conjecture 
that the two points which are *farthest apart* will lie on the smallest 
circle. Finding the two points farthest apart is at most O(n^2)  (anybody
know for sure?), after which finding the smallest circle is probably
O(n). It does seem like it ought to be easier, but I can't see it.

(We can make a little more speed in the common cases by looking only 
 at points lying on the convex hull. Finding the convex hull is 
 O(n log n) - I think.)

Ever helpfully :-),

garry wiegand   (garry@oak.cadif.cornell.edu - ARPA)
		(garry@crnlthry - BITNET)