MathGroup Archive 2004

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

Search the Archive

Re: Re: Smallest enclosing circle and other model versions

  • To: mathgroup at
  • Subject: [mg50096] Re: [mg50071] Re: [mg50062] Smallest enclosing circle and other model versions
  • From: "Janos D. Pinter" <jdpinter at>
  • Date: Sun, 15 Aug 2004 03:14:22 -0400 (EDT)
  • References: <> <>
  • Sender: owner-wri-mathgroup at


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.

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
>Andrzej Kozlowski
>Chiba, Japan

  • 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