MathGroup Archive 2004

[Date Index] [Thread Index] [Author Index]

Search the Archive

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


  • Prev by Date: Re: Log[4]==2*Log[2]
  • Next by Date: Re: Two questions
  • Previous by thread: Re: Re: Smallest enclosing circle
  • Next by thread: Histograms do not concur; why?