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).
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)
>> 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
> Andrzej Kozlowski
> Chiba, Japan
DrBob at bigfoot.com
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