Re: Re: Smallest enclosing circle and other model versions
- To: mathgroup at smc.vnet.net
- Subject: [mg50106] 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:35 -0400 (EDT)
- References: <200408130956.FAA03686@smc.vnet.net> <200408140550.BAA15284@smc.vnet.net> <6.1.2.0.1.20040814094213.01ccfe68@pop.hfx.eastlink.ca> <0AE5B675-EE04-11D8-ABBE-000A95B4967A@mimuw.edu.pl>
- Sender: owner-wri-mathgroup at wolfram.com
Andrzej [et al., interested in this discussion], - thanks for your reply; my comment was purely informational, no 'lecturing' was intended... :-) we look fwd to hearing from you. - I implemented the opt model in M5.0 mentioned in my previous note, and tried to solve several versions. One could also use an aggregated (non-smooth convex) constraint to replace the convex nonlinear ones, but this does not seem to be numerically advantageous. - Ray Koopman's second posting works nicely and faster than an NMinimize based approach, as can be expected: FindMinimum is an unconstrained local optimization routine, the problem is convex, and we have a good initial point (note that by the central limit theorem the mean point will be a good approx. of the true solution, in typical randomly generated tests). The runtime grows ~ linearly with the number of points, the solution for a 100000-point problem (generating points form a uniform distribution) is found in ~ 30 seconds on my P4 1.6 GHz desktop. The NMinimize based approach takes a little less time [already] for 1000 points. The general optimization approach I outlined in my previous note will work also for many more configuration analysis and design problems. Another example is the following: given a (convex or non-convex) set, and given the number of (unknown) points, find the best point arrangement s.t. the minimal pair-wise distance is maximized. Such models are of relevance in many areas, experimental design is one of these. This model requires a global optimization approach, and I actually have been using it in such tests. Regards, Janos Pinter At 12:10 PM 8/14/2004, you wrote: >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