Mathematica 9 is now available
Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2004
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2004

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

Search the Archive

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