[Date Index] [Thread Index] [Author Index]

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>