Re: Smallest enclosing circle
- To: mathgroup at smc.vnet.net
- Subject: [mg50569] Re: Smallest enclosing circle
- From: Steve Gray <stevebg at adelphia.net>
- Date: Fri, 10 Sep 2004 04:06:29 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
Matt, Thanks for your reply. I don't need speed since the number of my points is n=10 or less, because the subsequent steps are thousands of times slower, and it's unlikely that I can even do my other processes for n>8. I wanted a canned Mathematica function; not finding one, I wrote the (I think) simplest one: Draw all circles through 2 points and through 3 points in the convex hull and choose the smallest radius circle that encloses all points. This took about a page of code, which an expert could probably cut way down (and code a lot faster!). But it works and now I can get on to the research that really matters to me. Steve Gray On Thu, 9 Sep 2004 10:13:11 +0000 (UTC), Matt Pharr <matt at pharr.org> wrote: > >[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