MathGroup Archive 2004

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

Search the Archive

Re: Smalest enclosing circle

  • To: mathgroup at smc.vnet.net
  • Subject: [mg50146] Re: Smalest enclosing circle
  • From: Steve Gray <stevebg at adelphia.net>
  • Date: Tue, 17 Aug 2004 05:01:35 -0400 (EDT)
  • References: <cfi8tm$4p6$1@smc.vnet.net>
  • Sender: owner-wri-mathgroup at wolfram.com

On Fri, 13 Aug 2004 11:33:10 +0000 (UTC), Steve Gray <stevebg at adelphia.net> wrote:

>	Given n points in the  plane, I want to find the smallest
>enclosing circle. Does anyone have Mathematica code to do this?
>	I will be grateful for any tips.
>
>Steve Gray

	I want to thank everyone for their answers. 
	For Dr. Bob: I was not immediately able to install Draw Graphics because of some ambiguities
in the instructions and my own ignorance.
	The problem itself is nontrivial and there is no simple, correct solution which is also
efficient. Do a Web search on "smallest enclosing circle" and similar phrases and you will find many
leads. One claims there is a (complicated) linear time algorithm, but the more usual solution is
n*log(n).
	I have not found a canned answer for Mathematica. Fortunately my requirements are very easy:
a small number of points (not more than 20), and noncritical speed. The solution does not even have
to be the absolute smallest circle. The one thing that really matters is that no points may be
outside the circle. I wrote something very simple myself which solves the problem satisfactorily
(but not elegantly).
	I posted the question thinking that surely there would be lots of ready solutions already
coded. I'm sure that there are, but no one has come forth and publicized them.

Steve Gray


  • Prev by Date: FindMinimum and the minimum-radius circle
  • Next by Date: Combinatorica, NthPermutation, and a Sort behavior
  • Previous by thread: Re: Re: Smalest enclosing circle
  • Next by thread: ParametricPlot3D