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

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

• References:
  • Smalest enclosing circle
    • From: Steve Gray <stevebg@adelphia.net>
  • Re: Smalest enclosing circle
    • From: Andrzej Kozlowski <akoz@mimuw.edu.pl>