[Date Index]
[Thread Index]
[Author Index]
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/
Prev by Date:
**Re: Re: Smalest enclosing circle**
Next by Date:
**Re: Another Combinatorica loading problem**
Previous by thread:
**Re: Re: Smalest enclosing circle**
Next by thread:
**Re: Re: Smallest enclosing circle and other model versions**
| |