Path: utzoo!mnetor!uunet!lll-winken!lll-lcc!crawfis
From: crawfis@lll-lcc.aRpA (Roger A. Crawfis)
Newsgroups: comp.graphics
Subject: Re: Algorithm wanted: Circle enclosing points
Message-ID: <1593@lll-lcc.aRpA>
Date: 5 Apr 88 21:13:24 GMT
References: <4306@batcomputer.tn.cornell.edu>
Reply-To: crawfis@lll-lcc.llnl.gov.UUCP (Roger A. Crawfis)
Organization: Lab Comp Ctr, Lawrence Laboratory, Livermore Ca
Lines: 58
Keywords: convex hull, triangles

In article <4306@batcomputer.tn.cornell.edu> garry@oak.cadif.cornell.edu writes:
>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. 
>
...
>
>(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.)
>

True, but this is a degenerate case.
By the way this is first postin, so if I do anything wrong,
please flame and I will try to avoid future mistakes.

Points:
   1)  The circle will circumscribe the convex hull.
   2)  Given a nondegenerate convex polygon (convex hull), at least
       three points of it will lie on the smallest circumscribing
       circle.
   3)  Finding the convex hull takes O(n log n)
   4)  Finding the triangle with the largest radius from the
       convex hull can take O(m**2 log m).
   5)  The set of points comprising the convex hull may be (or
       may not be) substaintally smaller than n.


I like the centriod/farthest distance idea for large data sets and
when finding the absolute smallest circle is not neccessary.  However
if the data consists of a large cluster and a single point out in the
"boonies" then this can yield a circle twice the desired size.

A proposed solution.

  I.  Find the convex hull.
      oops-my I'm not sure my solution for the this works here.  So I'll
      let others illustrate how.  It's a well known problem. :(?.

 II.  Throw away any duplicate points.

III.  Find the radius by looking at the set of all possible triangles in
      the convex hull.  For a triangle with three sides of length a, b and c.

                         abc
             R = ------------------------
                 4*sqrt(s(s-a)(s-b)(s-c))

      where
   
             s = .5 * (a+b+c)

I know this is probably not the best (or completest) solution, but I
thought I needed to defend the triangle and convex hull answers.

Roger A. Crawfis