# N-dimensional Delaunay Tesselation Software Libraries

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...)

• Hi mirams, and welcome to scicomp! You may be interested in this question: scicomp.stackexchange.com/questions/770/…
– Paul
Jun 17, 2013 at 15:40
• 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. Jun 17, 2013 at 15:58
• popular question... also scicomp.stackexchange.com/questions/7664/… Jun 17, 2013 at 17:45
• Delaunay triangulation are typically derived from the the convex hull in higher dimensional space. See the qhull remark below. Jun 17, 2013 at 18:21
• 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/… Jun 17, 2013 at 18:33

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.

• Tested 4D, and that seems to work fine in QHull (I use it via scipy.spatial in python). Jun 17, 2013 at 16:27
• You won't beat qhull. I have used in via Scipy as well in up to 6 dimensions. Jun 17, 2013 at 18:20
• 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. Jun 17, 2013 at 19:50

This feature seems to be available in CGAL

• This also looks good. I'll try both Qhull and this. Thanks for the suggestions. 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.