Computing
the smallest enclosing disk in 2D |

Download Applet with Source (26 kb)

**Instructions:
*** By left-clicking in the blue area, you can set new points.

* By right-clicking points you can remove them.

* Note that they are also draggable.

* If you don't want to set many points manually, you can create a specified number of random points automatically.

* The Clear-Button removes all points.

* Finally pressing the Go-Button calculates and draws the minimal enclosing circle.

Notes:

The applet you
see above is my own implementation of Welzl's algorithm which computes the minimal
enclosing circle. I came around this algorithm while learning for my oral exam
in Computer Graphics and I thought why not trying to visualize it.

This algorithm was presented by Welzl in 1991 [1] and runs
(in contrast to most other algorithms for solving this prolbem) in linear time!

So
what it is all about? Let's say we have a set of n points in the plane,
we want to calculate the closed disk of smallest radius P
which contains all points in D(P).PLook at the picture left: we have a number of red points; the blue circle is the smallest one which contains all red points. So how to find this smallest circle (which means how to find its center and its radius) - that's the question! |

First of all, it's
easy to prove that such a *smallest enclosing disk* (sed)
is *unique*. Assume we have two smallest disks ** D_{1}**and

The
algorithm works now step by step: assume we know already a sed (smalled enclosing disk) ** D**
for n-1 points

1)

2)

In
fact, that's the main idea. This property along with the three following claims
allows us to calculate such a smallest enclosing disk in an iterative way:

Let * P* again be a set of n points,

(i) If there exists a disk containing

(ii) If p lies not in

(iii) If

With this information, one can implement this algorithm in a recursive way. Of course, as in all recursions, there are terminal or end cases in which you can calculate the solution directly. Here it is if we have 3 points only: a minimal circle in this case has the 3 points on the boundary and it's definitely determined (if the three points lie not on a common line!). In my implementation I also considered the cases with only 1 and 2 points. In fact I found it quite difficult to get the algorithm working - curius was that when I used arrays to hold the points the recursion works, but when I used vectors very strange things happened... Nevertheless, now it works and I hope you found my notes along the applet and its sources useful!

*Pseudocode:*

/* function
sed(P,R) |

*References:*

[1] Smallest enclosing disks (balls and ellipsoids), Emo Welzl, 1991

Sunshine, May 2008

This site is part of Sunshine's Homepage