Smallest enclosing ball of balls (miniball)

Introduction

This project provides code (currently C++ only) for finding the miniball (i.e., the smallest enclosing ball) of a given set of balls in d-dimensional Euclidean space. For d<10, the code is very fast: the miniball of one million balls in 3D is computed in less than a second on a modern PC. For d<20, it is still reasonably fast; beyond that it might be slow. This implementation is also very robust (not sensitive to degeneracies). The package has been developed at  ETH Zürich.

About the package

The source compiles using popular compilers, including  GNU GCC, MSVC++ and Metrowerks CodeWarrior. It works using float- or double-input, and is very robust to degenerate inputs; a large testsuite of "degenerate" examples is part of the package. Also included is a (independent) "provably rounding-error-free" version of the code, which works with arbitrary-precision rational arithmetic.

News and announcements

We have finally decided (22th January 2003) to make this library part of  CGAL, the Computational Geometry Algorithms library. From release 3.0 on,  CGAL contains our code as package  Min_sphere_of_spheres_d. For the impatient, download  CGAL and do

tar zxf CGAL-3.0.1.tar.gz
cd CGAL-3.0.1/examples/Min_sphere_of_spheres_d/
g++ benchmark.C -o benchmark -I ../../include/ -O3
./benchmark

The package is independent of CGAL in the sense that it is possible to use it without having the whole CGAL library installed. Refer to  CGAL and  GeometryFactory for information on licenses, or contact us (see bottom of this page).

Feel free to subscribe to the miniball-announce mailing list on the  project page. This is a (very low traffic) list informing about new releases.

Contact, references, and further information

In case you need any help, feel free to contact  Kaspar Fischer and/or  Bernd Gärtner.

Further information on some agorithms for the Miniball-problem can be found on  Kaspar Fischer's page; see also the references in the papers listed there.