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

• References:
  • Smalest enclosing circle
    • From: Steve Gray <stevebg@adelphia.net>
  • Re: Smalest enclosing circle
    • From: Andrzej Kozlowski <akoz@mimuw.edu.pl>