Re: Smalest enclosing circle

• To: mathgroup at smc.vnet.net
• Subject: [mg50071] Re: [mg50062] Smalest enclosing circle
• From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
• Date: Sat, 14 Aug 2004 01:50:19 -0400 (EDT)
• References: <200408130956.FAA03686@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

```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: Smalest enclosing circle
• Next by Date: Re: Help with parameter estimation
• Previous by thread: Re: Smalest enclosing circle
• Next by thread: Re: Re: Smalest enclosing circle