This page is about the Voronoi diagram of ellipses, under the Exact Computation Paradigm. The project started as part of my PhD. Applying exact computation on this problem turns out to be quite demanding, requiring handling of algebraic numbers of degree 184 (among other things). Fore more information, check out my publications.

C++ implementation

The source code lies in CGAL's cgal-public-dev github repository. Unfortunately, this version is no longer maintained (and also has nothing to do with modern C++ since I wrote it more than 10 years ago when I was still learning...). It is quite likely that changes are required for the code to compile with a more recent CGAL version.

However, I am in the process of refactoring it towards a C++17 version which is already pushing CGAL to its limits (e.g. missing move semantics :P) The new version also provides improved handling of algebraic points at infinity and high quality rendering via Asymptote). The code will soon be available (as work-in-progress) through my personal github repository.

Here are two screenshots of the old Qt4 demo:

More Screenshots (old Qt3 version)

Instructions for the old version:

To compile the source you need:

• The components algebrix, realroot and subdivix of the mmx library.
• The NTL library (you should choose GMP support when building).
• The CGAL library version 3.3.1.

WARNING: This public version of the source is outdated, and might not even compile with newer versions of SYNAPS/MMX. Please, use the newer version in CGAL's repository.

First public release (Dec 8, 2007): vorell-0.1.0.tar.gz