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.3"
Documentation:
MiniballTest.java
: A few tests take will help you understand how to use the library. Take a look at method TODO
for 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.)
On MacOS, do the following (not yet made on other ).
python
-folder.pip install setup.py
(you may need to use the --user
option or sudo
).pytest
(if you do not have it, install it through pip install pytest
) to see that it works and that all tests pass.On Linux or MacOS, the following steps will get you going:
# Get the source code
git clone https://github.com/hbf/miniball.git
cd miniball/csharp
# Compile an example, which generates random points and computes their miniball
dotnet build
# Run it on one million points in 3D
./example/bin/Debug/net7.0/example 1000000 3
To run unit tests:
dotnet test
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:
Many thanks go to the following people who have – sometimes substantially – contributed to the code:
pip
.