Path: utzoo!utgpu!water!watmath!watcgl!ksbooth
From: ksbooth@watcgl.waterloo.edu (Kelly Booth)
Newsgroups: comp.graphics
Subject: Re: Algorithm wanted: Circle enclosing points
Message-ID: <3905@watcgl.waterloo.edu>
Date: 6 Apr 88 18:20:58 GMT
References: <wWIfSMy00Xo3A5u1dC@andrew.cmu.edu> <496@etn-rad.UUCP> <3229@phri.UUCP>
Reply-To: ksbooth@watcgl.waterloo.edu (Kelly Booth)
Organization: U. of Waterloo, Ontario
Lines: 40

In article <3229@phri.UUCP> roy@phri.UUCP (Roy Smith) writes:
>jru@etn-rad.UUCP (John Unekis) writes:
>> Try finding the maximum and minimum x coordinates, then average to get the
>> center x. Do the same for y [...] look at the distances to those four
>> points [...] from the center x,y and take the largest distance as the radius.
>
>	It doesn't take much thought to show that this doesn't work.  Take,
>for example, the 5 points (0,-2), (2,0), (0,2), (-2,0), and (1.9,1.9).  The
>min and max x and y are -2 and 2, giving a center of (0,0) and a radius of
>2.  The fifth point, (1.9,1.9) does not fall within that circle.

The algorithm that was posted is garbage.  Assuming that the radius
calculation is extended to take a maximum over ALL points (Roy Smith
read the algorithm as taking the maximum over just max-min points,
which is what I read it as, but gave the poster the benefit of the
doubt and used the stronger condition), you still get the wrong
answer.

The algorithm computes a nice axis-oriented rectangular bounding box if
you keep just the max and min values.  The circle (with the extended
radius calculation) is a bounding circle, but neither the center or the
radius is guaranteed to be "good" in the sense of minimality.

Morals:

1.  Purported solutions posted to the net should be stated in an
algorithmic form not open to misinterpretation (this is, after all, a
group for people with some minimal familiarity with computing) so they
can be translated to a program directly.

2.  Solutions that do not include a reference to the literature or a
proof of correctness are often (in this group almost always) wrong in
trivial or major ways.

3.  Easy problems such as these hardly ever have naive, slick
solutions.  If they did, what person of any intelligence would post a
request for a solution to the net?  Slick solutions sometimes do exist,
but they usually require some insight, a detailed (sometimes messy)
proof of correctness, and almost always benefit from citations of
previous work that has been vetted in the literature.