Exact arithmetic

If you want detailed information about the research underlying Triangle's robustness, please see the Robust Predicates page.

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), and does not use extended precision internal floating-point registers (which Pentiums do!), then your output is guaranteed to be an absolutely true Delaunay or conforming Delaunay triangulation, roundoff error notwithstanding. The word `adaptive' implies that these arithmetic routines compute the result only to the precision necessary to guarantee correctness, so they are usually nearly as fast as their approximate counterparts.

Pentiums have extended precision floating-point registers. These must be reconfigured so their precision is reduced to memory precision. Triangle does this if it is compiled correctly. See the makefile and the Predicates on PCs page for details.

The exact tests can be disabled with the -X switch. On most inputs, this switch reduces the computation time by about eight percent, which is more than justified by the improved robustness. There are rare difficult inputs (having many collinear and cocircular vertices), however, for which the difference in speed could be a factor of two. Be forewarned that these are precisely the inputs most likely to cause bad behavior if you use the -X switch. Hence, the -X switch is not recommended.

Unfortunately, these routines don't solve every numerical problem. Exact arithmetic is not used to compute the positions of new vertices, because the bit complexity of vertex coordinates would grow without bound. Hence, segment intersections aren't computed exactly; in very unusual cases, roundoff error in computing an intersection point might actually lead to an inverted triangle and an invalid triangulation. (This is one reason to compute your own intersection points in your .poly files.) Similarly, exact arithmetic is only partly used to compute the vertices of the Voronoi diagram.

Another pair of problems not solved by the exact arithmetic routines is underflow and overflow. If Triangle is compiled for double precision arithmetic, I believe that Triangle's geometric predicates work correctly if the exponent of every input coordinate falls in the range [-148, 201]. Underflow can silently prevent the orientation and incircle tests from being performed exactly, while overflow typically causes a floating exception.

Return to Triangle page.
jrs@cs.berkeley.edu