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