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: Smalest enclosing circle

  • To: mathgroup at smc.vnet.net
  • Subject: [mg50071] Re: [mg50062] Smalest enclosing circle
  • From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
  • Date: Sat, 14 Aug 2004 01:50:19 -0400 (EDT)
  • References: <200408130956.FAA03686@smc.vnet.net>
  • Sender: owner-wri-mathgroup at wolfram.com

On 13 Aug 2004, at 11:56, Steve Gray wrote:

> *This message was transferred with a trial version of CommuniGate(tm) 
> Pro*
> 	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
>
>

The three diemensional analogue of this problem was posted on this list 
in 1999. I  sent a description of the algorithm with proof but without 
an implementation. I believe the original poster wrote one himself. 
Here is a slighlty modified extract form my (final) posting:


We first consider all pairs of points from our set and all circles 
which have any
such pair as a diameter. We then consider all circles circumscribed on 
any three points out of our set. We then look among them for
circles enclosing all the points of our set and then take the smallest 
such circle.

The proof is as follows. Consider the smallest circle containing all 
the points. If it passes only
through one or zero points of our set we can certainly make it smaller 
(without leaving this
point) so that it still encloses all the points. If it passes through 
only two points of our set, which are not on its diameter,
we can make it slightly smaller without leaving these points in such a 
way that it still encloses all the points. Hence the minimal
circle must either pass through three points or have two points on the 
diameter.


Andrzej Kozlowski
Chiba, Japan
http://www.mimuw.edu.pl/~akoz/


  • Prev by Date: Re: Smalest enclosing circle
  • Next by Date: Re: Help with parameter estimation
  • Previous by thread: Re: Smalest enclosing circle
  • Next by thread: Re: Re: Smalest enclosing circle