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)
• 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.

is a fair chance that I may soon find myself thinking about problems
involving optimisation, and then I will remember about Frank Kampas's

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/
>