The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

Fast Robust Predicates for Computational Geometry

Many computational geometry applications use numerical tests known as the orientation and incircle tests. The orientation test determines whether a point lies to the left of, to the right of, or on a line or plane defined by other points. The incircle test determines whether a point lies inside, outside, or on a circle defined by other points.

Each of these tests is performed by evaluating the sign of a determinant (see the figure below). The determinant is expressed in terms of the coordinates of the points. If these coordinates are expressed as single or double precision floating-point numbers, roundoff error may lead to an incorrect result when the true determinant is near zero. In turn, this misinformation can lead an application to fail or produce incorrect results.

  • Download Files (local site)
  • Offical Site

    Problem Links

    Robust Geometric Primitives (7)

    This page last modified on 2008-07-10 .