Re: Re: Smallest enclosing circle and other model versions
- To: mathgroup at smc.vnet.net
- Subject: [mg50101] Re: [mg50071] Re: [mg50062] Smallest enclosing circle and other model versions
- From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
- Date: Sun, 15 Aug 2004 03:14:27 -0400 (EDT)
- References: <200408130956.FAA03686@smc.vnet.net> <200408140550.BAA15284@smc.vnet.net> <6.1.2.0.1.20040814094213.01ccfe68@pop.hfx.eastlink.ca>
- Sender: owner-wri-mathgroup at wolfram.com
Of course I never for a moment imagined mine was an efficient approach. After all, I have never worked on optimisation of any kind and my interest in this problem was motivated by pure curiosity. The method can certainly be improved: for a start one can consider only the convex hull of the set of points and I am sure that there are other geometric simplification that can be made, but I would not want to spend much time thinking about them. The virtue of the approach is its simplicity: anyone with very moderate programming skills should be able to implement it. Also, when I originally considered this problem Mathematica was at version 3, there was no NMinimize etc. Today the situation is very different, as is the case with several other areas where Mathematica is used. Having said that, I am very glad to have received your message. There is a fair chance that I may soon find myself thinking about problems involving optimisation, and then I will remember about Frank Kampas's and your work. Andrzej On 14 Aug 2004, at 15:04, Janos D. Pinter wrote: > > > 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