# Best incremental multidimensional Delaunay tessellation algorithm

I'm looking for a specific type of Delaunay tessellation algorithm.

The algorithm should be:

• incremental so that I can add new sites inside known simplexes (i.e. no searching for the right simplex is necessary)
• usable with a high number of dimensions (100 or more)
• usable with a high number of sites (10000 or more)
• (bonus) parallelizable to multiple cores

So basically I want to start off with a single simplex, add a site to split the simplex, and then iteratively select a simplex, add a site into it, and fix the Delaynay tesselation.

Am I looking for a unicorn here, or does something like this actually exist? I've been using Devijver and Dekesel's algorithm, but it's time complexity in number of sites and dimensions is no good enough.

• 100 dimensions seems way too high for current technology. The libraries I know of (e.g. CGAL.org ) might go up to 6 dimensions while remaining practical. – Ronaldo Carpio Apr 4 '14 at 13:45
• For some intuition about how difficult meshing would be in such high dimensions, consider that a 100 dimensional box contains $2^{100} \approx 10^{30}$ corners. Since a floating point number takes up 32 bits, by my calculations this would require on the order of $10^{20}$ terrabytes of storage. – Nick Alger Apr 4 '14 at 17:49
• However, for a 100 dimensional simplex, it only has 101 vertices, which is far more manageable than a 100 dimensional hypercube. In this sense, what Juha is asking for is not as absurd. – Victor Liu Apr 4 '14 at 22:37