Computing Delaunay complexes can be sensitive to numerical instabilities, especially in higher dimensions. I would like to know how much I can rely on Mathematica's answers when using DelaunayMesh. There are two questions:

  1. Are exact computations used when constructing the mesh? Or is the computation numerical?

  2. How does it deal with non-generic cases, when we have, e.g., four points lying on a circle? I know that it triangulates the squares (or n-gons in general). But is it done just arbitrarily or is there some careful treatment implemented, like the Simulation of Simplicity method?

  • 1
    $\begingroup$ Good question. Have a look into the documentations of the libraries "tetgen" and "triangle"; as far as I know, those are used as backends for dimension 3 and 2, respectively. $\endgroup$ Jun 16 at 18:57

This only answers your first question.

I believe that DelaunayMesh will use the Triangle software through TriangleLink, when working in two dimensions.

While Triangle works with floating point numbers, The Triangle documentation has a section dedicated to exact arithmetic:

While the computation is numerical, Triangle does seem to offer some guarantees. Quoting from the page above:

Triangle uses adaptive exact arithmetic to perform what computational geometers call the 'orientation' and 'incircle' tests. If the floating- point arithmetic of your machine conforms to the IEEE 754 standard (as most workstations do), ... then your output is guaranteed to be an absolutely true Delaunay or conforming Delaunay triangulation, roundoff error notwithstanding.

For 3D, TetGen is used. See also the old website. According to its manual, TetGen uses the same system for exact arithmetic as Triangle.


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.