Math Forum

From: haoyuep@aol.com (Dan Hoey)
Date: May 18, 2004 9:38 PM
Subject: Re: smallest disk covering a set of points

On 18 May 2004, Carlos Moreno wrote:

>Carlos Moreno wrote:

>>And no, I don't think it is clear at all that you can do it by
>>divide-and-conquer -- how do you merge the results of two subsets?
>>Remember, the points are not ordered, so the two convex hulls could
>>intersect, not intersect, one entirely included in the other one.
>>I'm not sure it is trivial to obtain O(N logN) this way.

If you are talking about the smallest disc problem, I don't see any
way of doing divide and conquer.  If you are talking about calculating
the convex hull, divide and conquer works just fine.

>Actually, I think I was mistaken on this -- it is probably very easy
>to do it by divide-and-conquer; I was concentrating on the fact that
>the points are unordered;

When the time comes to merge convex hulls, you have ordered the points
on the separate convex hulls.  That is, you have produced the convex
hulls as a list of their vertices in cyclic order.

>but the thing is, you still can divide the set into two with a
>straight line "in the middle" -- this will guarantee that the two
>convex hulls will not intersect (or intersect in just a point).

You can divide the set by the median x value in linear time (and if
you mean something else by "in the middle" you may not have guaranteed
N log N time for the algorithm.  But it is not necessary to do this.
You can calculate the convex hull of two convex polygons (with their
vertices given in cyclic order) in O(V) time, where V is the total
number of vertices.  This works whether the polygons overlap or not.
It even works if they poke out of each other in lots of places.  You
just take a walk around the polygons in angle order and merge them.
Easy.

>So yes, what you suggest is a valid approach to obtain the convex
>hull in O(NlogN) (and it *is* optimal in terms of big O complexity)

It's optimal for finding the convex hull, but not for finding the
smallest enclosing disc.  I was quite surprised to hear that the
smallest enclosing disc could be found in linear time, but there
are enough references to Megiddo's 1983 result that I believe it.
Unfortunately, the closest I've found to a description of the
algorithm online is http://www.personal.kent.edu/~rmuhamma/
Compgeometry/MyCG/CG-Applets/Center/centercli.htm , which
unfortunately leaves out a part of the algorithm.  Still, the linear
time fractioning algorithm is a wonderful idea, and I'm sure the
missing part is "a simplified part of the algorithm as a whole", only
I can't figure it out.

David Eppstein mentioned Bernd Gaertner's software at
http://www2.inf.ethz.ch/personal/gaertner/miniball.html , which
appears to me to require linear expected time, but I don't know
what its worst-case performance is.

Dan Hoey
haoyuep@aol.com