A C++ and Java library to compute the miniball (a.k.a. min-circle, min-sphere, smallest enclosing sphere, etc.) of a point set.
The code works for points in arbitrary dimension. It runs very fast in low dimensions and is practically efficient up to dimensions 10,000. The implementation is based on the algorithm from the paper "Fast Smallest-Enclosing-Ball Computation in High Dimensions" by Kaspar Fischer, Bernd Gärtner, and Martin Kutz (Proc. 11th European Symposium on Algorithms (ESA), p. 630-641, 2003).
This project is dedicated to Martin Kutz†.
On a 2.66 GHz Intel Core i7 MacBook Pro, the code performs as follows:
The chart shows the time in seconds (y-axis) needed for the computation of the miniball of n random points (x-axis) in dimensions d (3, 5, or 10 in this chart).
The code is well-tested and its underlying algorithm should be numerically stable. By "numerically stable" we mean that even for points in degenerate position – like all on a line, all on a circle, identical points in the input, etc. – the algorithm will (i) terminate, (ii) be fast, (iii) provide an accurate result.
Please report any problems you may find as tickets.
You can either download the latest JAR file from TODO or use a build system like Maven or Graddle, or SBT (for Scala users).
Maven dependency:
<dependency>
<groupId>com.dreizak</groupId>
<artifactId>miniball</artifactId>
<version>1.0.1</version>
</dependency>
SBT dependency:
libraryDependencies += "com.dreizak" % "miniball" % "1.0.1"
Documentation:
- Project information
- JavaDoc
MiniballTest.java: A few tests take will help you understand how to use the library. Take a look at methodTODOfor a simple example.
On Linux or MacOS, the following steps will get you going: (Notice that the Boost library that the instructions below download is only used in this example to generate some input points; the library as such does not depend on it.)
# Get the source code
git clone https://github.com/hbf/miniball.git
cd miniball/cpp/test
# Compile an example, which generates random points and computes their miniball
g++ -I../main example.C -o example -O3
# Run it on one million points in 3D
./example 1000000 3(More documentation to come. Contact us in case you run into any problems.)
The C++ code is written using templates and allows the number type to be specified as a template argument.
However, please only use double as the number type, as is illustrated in the example program example.C (see line typedef double FT).
The code will not run correctly if you use float.
The code is available under the Apache 2 License, which is explained [here](http://www.tldrlegal.com/license/apache-license-2.0-(apache-2.0).
If you use the code in your project/product, please drop us a note – we are always interested in learning about new applications!
Authors:
- Martin Kutz, FU Berlin
- Kaspar Fischer, ETH Zurich
- Bernd Gärtner, ETH Zurich
Many thanks go to the following people who have – sometimes substantially – contributed to the code:
- Thomas Otto (University of Hamburg) for submitting several compiler fixes (g++ 4.7 and 4.5 on SUSE Linux 12.2 and 11.3) and for introducing generic point and point coordinate accessors in the code.
- For small dimensions like 2D or 3D, Bernd Gärtner's code, which is based on Welzl's algorithm, may be faster.
- The Computational Geometry Algorithms Library (CGAL) contains both floating-point and arbitrary-precision arithmetic implementations of several bounding sphere algorithms. Among then, there is an algorithm to compute the minsphere of spheres (not just points as input). See the Chapter on Bounding Volumes.