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/
- Follow-Ups:
- Re: Re: Smallest enclosing circle and other model versions
- From: "Janos D. Pinter" <jdpinter@hfx.eastlink.ca>
- Re: Re: Smalest enclosing circle
- From: DrBob <drbob@bigfoot.com>
- Re: Re: Smallest enclosing circle and other model versions
- References:
- Smalest enclosing circle
- From: Steve Gray <stevebg@adelphia.net>
- Smalest enclosing circle