I have a set of known points/nodes irregularly spaced in N-Dimensional space (N>=2), and I would like a way to generate the Delaunay triangulation of these points, and return the corresponding elements.

Are there any existing meshing libraries that will do an N-D Delaunay triangulation?

(I am doing this because I want to use the meshed elements as a basis for linear interpolation at any point in space. My dimension is currently handled by a C++ class templated over dimension if that makes any difference to suggestions...)

  • $\begingroup$ Hi mirams, and welcome to scicomp! You may be interested in this question: scicomp.stackexchange.com/questions/770/… $\endgroup$
    – Paul
    Jun 17, 2013 at 15:40
  • $\begingroup$ Thanks for the link, I was hoping to avoid writing my own mesher. Tetgen (for 3D) runs to a lot of lines of code. It seems like a problem that must have been solved many times. $\endgroup$
    – mirams
    Jun 17, 2013 at 15:58
  • $\begingroup$ popular question... also scicomp.stackexchange.com/questions/7664/… $\endgroup$
    – clipper
    Jun 17, 2013 at 17:45
  • $\begingroup$ Delaunay triangulation are typically derived from the the convex hull in higher dimensional space. See the qhull remark below. $\endgroup$
    – meawoppl
    Jun 17, 2013 at 18:21
  • $\begingroup$ 3D is not that hard, but for 4D it is extremely difficult when refining, I asked a question on MathOverflow, but no answer yet: mathoverflow.net/questions/130878/… $\endgroup$
    – Shuhao Cao
    Jun 17, 2013 at 18:33

3 Answers 3


I think you can do this using convex hull software (e.g. QHull) via the lifting algorithm. At least, the documentation of matlab's "delaunayn" command seems to indicate as much.

  • 2
    $\begingroup$ Tested 4D, and that seems to work fine in QHull (I use it via scipy.spatial in python). $\endgroup$
    – Ethan Coon
    Jun 17, 2013 at 16:27
  • 1
    $\begingroup$ You won't beat qhull. I have used in via Scipy as well in up to 6 dimensions. $\endgroup$
    – meawoppl
    Jun 17, 2013 at 18:20
  • $\begingroup$ Hmmm - this from qhull.org/news/qhull-news.html isn't ideal: "All users In 3-d and higher, option 'Qt' does not produce conforming triangulations for adjacent, non-simplicial facets. For example, if you have a regular, 3-d array of input sites, their Delaunay triangulation consists of cubes. Option 'Qt' will triangulate each cube into tetrahedra. Within each cube, the triangulation is consistent, but it is not necessarily consistent between adjacent cubes [C. Bertoglio; C. de Visser]. How to fix this problem is unknown." Worth a try though, I'll see how I get on. $\endgroup$
    – mirams
    Jun 17, 2013 at 19:50

This feature seems to be available in CGAL

  • $\begingroup$ This also looks good. I'll try both Qhull and this. Thanks for the suggestions. $\endgroup$
    – mirams
    Jun 17, 2013 at 19:56

I have also found distmesh in Matlab that appears to be able to do this:

Distmesh Homepage

It does tesselations for finite element meshes (via QHull) but with a nice interface for defining areas / surfaces based on distance functions. Better for cases where you want to define a surface mathematically and do not mind where the internal nodes are.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.