[Date Index]
[Thread Index]
[Author Index]
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
Prev by Date:
**Re: How to solve a simple Trig cofunction?**
Next by Date:
**Re: sorry, but more q's on random numbers**
Previous by thread:
**Re: problem with ExpectedValue[xx-x, PoissonDistribution[m],x]**
Next by thread:
**Re: Re: Smallest enclosing circle**
| |