The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

Exact Geometric Computation (EGC)

The Core Library is based on a novel number core. This library provides an API which defines four levels of numerical accuracy. The main intent of this implementation was to support the Exact Geometric Computation (EGC) approach to numerically robust algorithms. Nevertheless, it is quite general and can be used in any other application where numerical accuracy must be guaranteed.

Our library provides users with a simple and natural numerical API to support the following concepts of accuracy:

* LEVEL I: Machine Accuracy. This can be identified with the IEEE standard.

* LEVEL II: Arbitrary Accuracy. If you specify 200 bits of accuracy (in relative or absolute terms), this guarantees that you will not experience overflow or underflow until you exceed 200 bits. This is similar to what any computer algebra system (say, Maple) gives you.

* LEVEL III: Guaranteed Accuracy. This is the novel part: thus, you can specify 1 relative bit or 10 absolute bits of accuracy at this level. Note that 1 relative bit ensures that you get exact signs of real numbers, the critical idea in Exact Geometric Computation.

* LEVEL IV: Mixed Accuracy. This localizes the the previous accuracy levels to individual variables, for better control of accuracy and efficiency.

  • Download Files (local site)
  • Offical Site

    Problem Links

    Robust Geometric Primitives (8)

    This page last modified on 2008-07-10 .