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 your machine's internal floating-point registers are of the same length as the floating-point words stored in memory (which is not true of PCs unless you reconfigure the processor first), 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.

The exact tests can be disabled with the -X switch. On most inputs, disabling exact arithmetic will cause a small improvement (roughly eight percent) in speed, and create the possibility (albeit small) that Triangle will fail to produce a valid mesh. There are rare difficult inputs (having many collinear and cocircular points), however, for which the difference in speed could be as large as fifty percent. Be forewarned that these are precisely the inputs most likely to cause errors if you use the -X switch. Hence, the -X switch is not recommended.

Unfortunately, the exact arithmetic routines don't solve every numerical problem. Exact arithmetic is not used to compute the positions of new points (such as segment intersection points and Steiner points), because the bit complexity of point 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, though I've never seen such an error actually occur.)

Similarly, exact arithmetic is not used to compute the vertices of the Voronoï diagram.

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

Warning: The exact arithmetic code will not actually be exact, and hence Triangle is not guaranteed to be robust, on a processor that uses extended precision internal floating-point registers, such as the Intel 80486 and Pentium, unless the processor is configured to round internally to double precision. See the Predicates on PCs page for details.

Return to Triangle home page.
jrs@cs.cmu.edu