3
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • 5
    $\begingroup$ 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. $\endgroup$ – Ronaldo Carpio Apr 4 '14 at 13:45
  • 2
    $\begingroup$ 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. $\endgroup$ – Nick Alger Apr 4 '14 at 17:49
  • $\begingroup$ 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. $\endgroup$ – Victor Liu Apr 4 '14 at 22:37
1
$\begingroup$

As @NickAlger alludes, the incremental delaunay approach can scale exponentially with the dimension of the space, even if the final tesselation has few facets. Even if some computable solutions exist for special cases, it's unlikely that any practical algorithms exist for general tesselations, which seems to be what you're looking for.

|cite|improve this answer
$\endgroup$
0
$\begingroup$

Not sure if this is what you're looking for but try http://www.qhull.org/ .

It's the library used by Matlab, Octave and scipy.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ Qhull explicitly does not support more than 7 dimensions for tesselation. $\endgroup$ – LKlevin May 5 '14 at 9:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.