Re: Re: Smallest enclosing circle and other model versions
- To: mathgroup at smc.vnet.net
- Subject: [mg50096] Re: [mg50071] Re: [mg50062] Smallest enclosing circle and other model versions
- From: "Janos D. Pinter" <jdpinter at hfx.eastlink.ca>
- Date: Sun, 15 Aug 2004 03:14:22 -0400 (EDT)
- References: <200408130956.FAA03686@smc.vnet.net> <200408140550.BAA15284@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Andrzej, the approach you suggest will lead to rapidly increasing comp'l demands (in terms of the no. of relations/circles to consider). By contrast, a numerical optimization approach for k(>=4) points in R^n n>=2 has n+1 vars (embedding circle centre and radius), a linear obj fct (embedding circle radius), k convex nonlinear constraints (each point should be within the embedding circle), and - in full generality - 2n box constraints (regarding the location of the centre). An analogous approach would work also for variants of this model, including non-convex ones. Frank Kampas and I wrote several papers on related but much more difficult models such as e.g. finding the minimal embedding circle for arbitrary (non-uniform size) circles. We used our package MathOptimizer Professional to solve those models (and we have also tried other optimizers to do the same). These papers are to appear; and are available from us. Regards, Janos Pinter At 02:50 AM 8/14/2004, Andrzej Kozlowski 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/
- References:
- Smalest enclosing circle
- From: Steve Gray <stevebg@adelphia.net>
- Re: Smalest enclosing circle
- From: Andrzej Kozlowski <akoz@mimuw.edu.pl>
- Smalest enclosing circle