Robust Adaptive Floating-Point Geometric Predicates Jonathan Richard Shewchuk School of Computer Science Carnegie Mellon University Pittsburgh, Pennsylvania 15213 Fast C implementations of four geometric predicates, the 2D and 3D orientation and incircle tests, are publicly available. Their inputs are ordinary single or double precision floating-point numbers. They owe their speed to two features. First, they employ new fast algorithms for arbitrary precision arithmetic that have a strong advantage over other software techniques in computations that manipulate values of extended but small precision. Second, they are adaptive; their running time depends on the degree of uncertainty of the result, and is usually small. These algorithms work on computers whose floating-point arithmetic uses radix two and exact rounding, including machines that comply with the IEEE 754 floating-point standard. Timings of the predicates, in isolation and embedded in 2D and 3D Delaunay triangulation programs, verify their effectiveness. Proceedings of the Twelfth Annual Symposium on Computational Geometry (Philadelphia, Pennsylvania), pages 141-150, ACM, May 1996. PostScript (310k). Paper available through the URL http://www.cs.berkeley.edu/~jrs/papers/robust-predicates.ps For additional details and associated software, see the Web page http://www.cs.cmu.edu/~quake/robust.html BibTeX entry: @inproceedings{shewchuk96a, author = {Jonathan Richard Shewchuk}, title = {Robust {A}daptive {F}loating-{P}oint {G}eometric {P}redicates}, booktitle = {Proceedings of the Twelfth Annual Symposium on Computational Geometry}, publisher = {Association for Computing Machinery}, pages = {141--150}, month = may, year = 1996 }