Re: smallest disk covering a set of points

From: Carlos Moreno (moreno_at_mochima_dot_com_at_xx.xxx)
Date: 05/16/04 

Date: Sun, 16 May 2004 09:26:28 -0400

Phil Holman wrote:

>>>First iteration should be to pick a pair of points the greatest
>>>distance apart and draw a circle where these points are
>
> diametrically
>
>>>opposite. If this is not the solution then the next iteration will
>
> be
>
>>>to consider the point furthest outside of the circle and draw a
>
> circle
>
>>>that goes through all three points. I haven't checked out to see if
>>>this is the final solution but I can't see why it shouldn't be.
>>
>>It's not. I posted a counter-example to this algorithm in some other
>>branch of this thread.
>
>
> One more iteration. If there is a 4th point outside the second circle on
> the opposite side of the circle from the 3rd point, then draw a circle
> through points 3 and 4 and point 1 or 2 (whichever is furthest from
> point 4). Try that.

In my experience, from a Computational Geometry course taken
a few years ago, this smells way too fishy -- this "one more
iteration" when an algorithm is found to fail more often fails
than works.

Intuitively, I would tend to think that *iterating* the way you
describe until finding a solution should work (i.e., the
iterative process *should* converge to a solution). But in
this case, I'm far from convinced that it will lead to *the*
solution (i.e., my intuition tells me that it will converge to
a disk that finally encloses all the points, but that will not
necessarily be the smallest disk). And yes, that was *the main*
thing that I learned from that Computational Geometry course:
in geometry problems, intuition virtually always betrays us
and leads to incorrect algorithms. (for instance, with
convex hulls -- there was a famous algorithm to compute the
C.H. of a set of points in linear time; the algorithm was
published, with a two-page proof of correctness. *six years*
later, a counter-example was published, showing that the
algorithm was incorrect (later, people analyzed the proof
and found out why it was also wrong). Even to date, more
than half of the algorithms to compute the convex hull of
a simple polygon in linear time, are incorrect -- but they're
all so intuitive, and it is so obvious that they do work.

Carlos 

--

Relevant Pages

  • Short koan-like code snippets (was: coerce for arbitrary types)
    ... (defun bfs6 (test children pending) ... The algorithm seems to be a tail-recursive expression of what ... I don't like using tail recursion to emulate iteration, ...
    (comp.lang.lisp)
  • Iterative subspace decomposition
    ... Subspace Tracking," IEEE Transactions on Signal Processing, vol. 43, ... the PASTd algorithm does not produce orthogonal ... it is not producing the eigendecomposition I ...
    (sci.math.num-analysis)
  • Re: OO Style with Ada Containers
    ... The most important part of STL is the notion of range-based iteration. ... Every single algorithm that iterates over something gets a pair of ... But there's nothing that precludes that in Ada: ... procedure Generic_Algorithm (First, Back: Cursor); ...
    (comp.lang.ada)
  • Re: smallest disk covering a set of points
    ... > Is there a fast algorithm for finding the smallest disk that covers a set ... > circle till I hit the outermost point, ... Find the minimal set of points which generates the convex hull ... Which looks like a linear time minimum circle finding algorithm to me. ...
    (comp.programming)
  • Re: Help with bisectors
    ... Once you get your implementation ready you'll see how roundoff errors totally breaks your algorithm in most real cases, and you'll spend months, many, trying to fix it with little success, unless you happen to have a lot of experience in robust geometric computing. ... I strongly recommend that you simplify the problem by linearizing the circular arcs. ... (precisely line-arc bisectors and arc-arc ... circle-circle bisectors are ellipses, or hyperbolas, if they are unconnected. ...
    (comp.graphics.algorithms)
Loading