Re: Smallest enclosing circle
- To: mathgroup at smc.vnet.net
- Subject: [mg50546] Re: Smallest enclosing circle
- From: Matt Pharr <matt at pharr.org>
- Date: Thu, 9 Sep 2004 05:19:22 -0400 (EDT)
- References: <cfq404$r9m$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
[No mathematica code below, but some useful background.] This problem actually comes up frequently on comp.graphics.algorithms, frequently enough that there's a FAQ entry there about it. A lot of one's intuition about this problem is often wrong. To wit: <http://www.magic-software.com/CgaFaq.pdf> 1.5 How can the smallest circle enclosing a set of points be found? This circle is often called the minimum spanning circle. It can be computed in O(n log n) time for n points. The center lies on the furthest point Voronoi diagram. Computing the diagram constrains the search for the center. Constructing the diagram can be accomplished by a 3D convex hull algorithm; [...] In fact, the smallest circle can be computed in expected time O(n) by first applying a random permutation of the points. The general concept applies to spheres as well (and to balls and ellipsoids in any dimension). The algorithm uses a linear programming approach, proved by Emo Welzl in [Wel91]. Code developed by Bernd Gaertner is available (GNU General Public License) at http://www.inf.ethz.ch/ -matt -- Matt Pharr matt at pharr.org <URL:http://graphics.stanford.edu/~mmp> ======================================================================= In a cruel and evil world, being cynical can allow you to get some entertainment out of it. --Daniel Waters
- Follow-Ups:
- Re: Re: Smallest enclosing circle
- From: DrBob <drbob@bigfoot.com>
- Re: Re: Smallest enclosing circle
- From: DrBob <drbob@bigfoot.com>
- Re: Re: Smallest enclosing circle