Fast computation of the smallest enclosing ball of a point set, in low or moderately high dimensions.
Java C++ C Perl
Latest commit f07c470 Dec 5, 2016 @hbf hbf Merge pull request #21 from IntellectualKitty/const-point-set
Constant point set

README.md

Miniball

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†.

Speed

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).

Stability

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.

Getting started (Java)

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:

Getting started (C++)

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.)

Float or double?

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.

License

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 & acknowledgements

Authors:

Many thanks go to the following people who have – sometimes substantially – contributed to the code:

Links