Path: utzoo!utgpu!water!watmath!clyde!att-cb!osu-cis!tut.cis.ohio-state.edu!mailrus!umix!uunet!mcvax!ruuinf!markov
From: markov@ruuinf.UUCP (dr.m.h. overmars)
Newsgroups: comp.graphics
Subject: Re: Algorithm wanted: Circle enclosing points
Summary: Errors and new solutions
Message-ID: <406@ruuinf.UUCP>
Date: 15 Apr 88 15:58:41 GMT
References: <494@eos.UUCP> <682@sun.soe.clarkson.edu> <5256@venera.isi.edu>
Organization: Univ of Utrecht, Dept of CS
Lines: 34

In article <5256@venera.isi.edu>, lmiller@venera.isi.edu (Larry Miller) gives
a solution to the smallest enclosing circle problem. I can't see why
this solution works (unless I misunderstand the notion of centroid).
You can alsways add points to a set that will lie on one side on the
convex hull without changing the bounding circle. But this must change the
centroid and, hence, the circle found.

Here are two simple, linear time solutions that do give enclosing
circles but not neccessarily minimal ones:

1) Find the bounding box (by determining minimal and maximal x- and y-values.
   Take the middle as center and as radius the distance to a vertex. Normally
   the circle found will be too large, but not that much too large.

2) Start with the minimal circle of three points (either the circle with
   the three points on the boundary or with two on opposite sides). Now
   one after the other add the points and every time compute the minimal
   circle that encloses the previous found circle and the new point.

A O(n log n) solution has been given quite some time ago by Shamos, using
farthest-point Voronoi diagrams. One of the references is:

M.I. Shamos and D Hoey, Closest-point problems, Proc. 16th Annual IEEE
       Symposium on Foundations of Computer Science (FOCS), 1975, pp. 151-162.

For some other heuristical solution to this problem and related ones see:

K.J. Supowit, Grid heuristics for some geometric covering problems, in:
       F.P. Preparata (Ed.) Advances in Computing research, vol 1:
       computational geometry, JAI press, 1983, pp. 215-234.

I hope this answers all the questions about the problem.

Mark Overmars.