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

  • To: mathgroup at smc.vnet.net
  • Subject: [mg50099] Re: [mg50071] Re: [mg50062] Smalest enclosing circle
  • From: DrBob <drbob at bigfoot.com>
  • Date: Sun, 15 Aug 2004 03:14:25 -0400 (EDT)
  • References: <200408130956.FAA03686@smc.vnet.net> <200408140550.BAA15284@smc.vnet.net>
  • Reply-to: drbob at bigfoot.com
  • Sender: owner-wri-mathgroup at wolfram.com

Andrzej is quite right, and my code was returning larger circles than necessary much of the time. I shouldn't have squelched the error message from FindMinimum, but I thought it was just a precision issue.

The optimum circle contains two points of the set on a diameter OR it contains at least three points of the set (or both).

Bobby

On Sat, 14 Aug 2004 01:50:19 -0400 (EDT), Andrzej Kozlowski <akoz at mimuw.edu.pl> wrote:

> 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/
>
>
>



-- 
DrBob at bigfoot.com
www.eclecticdreams.net


  • Prev by Date: Re: How does a notebook get its own filename or directory?
  • Next by Date: Re: Re: Re: How to set linewidth in 3-D graphics?
  • Previous by thread: Re: Smalest enclosing circle
  • Next by thread: Re: Re: Smallest enclosing circle and other model versions