Filtered Exact Arithmetic for Robust Geometric Computation

159 concepts110 papers1 proposal

Theoretical computational geometry assumes a world of perfect real numbers. In this idealized setting, lines intersect at exact coordinates, and algorithms make decisions based on flawless spatial relationships. However, when these algorithms are implemented on modern hardware using IEEE 754 floating-point arithmetic, this assumption shatters.

Floating-point numbers have finite precision. Rounding errors, though small individually, accumulate and cause catastrophic failures in geometric code. As noted by Dey et al., standard floating-point arithmetic frequently leads to software crashes or infinite loops because it cannot reliably resolve ambiguous spatial configurations. The core issue is a mismatch between numerical calculations and combinatorial logic: a rounding error can cause an algorithm to believe a point lies on the wrong side of a line, violating topological invariants and breaking the underlying data structure.

To build reliable geometry pipelines without sacrificing performance, researchers have developed a paradigm centered on robust geometric predicates, filtered exact arithmetic, and representation-aware algorithm design.

The Core Mechanism: Geometric Predicates

Most geometric algorithms do not actually need to know the exact coordinates of every intersection or curve. Instead, they rely on discrete decisions called geometric predicates. A typical predicate answers a qualitative question, such as:

  • Orientation: Is point $C$ to the left of, to the right of, or exactly on the directed line segment $AB$?
  • In-Circle: Does point $D$ lie inside, outside, or on the boundary of the circle defined by points $A$, $B$, and $C$?

Mathematically, these predicates are evaluated by computing the sign of a determinant. If the determinant is positive, the answer is $+1$; if negative, $-1$; if exactly zero, the points are collinear or cocircular (a degenerate configuration).

Floating-point arithmetic fails when the true value of the determinant is very close to zero. A slight rounding error can flip the sign from positive to negative, causing the algorithm to make a logically inconsistent choice.

Why Filtered Exact Arithmetic Works

The most naive way to ensure robustness is to replace all floating-point operations with exact arithmetic (such as arbitrary-precision rationals or integers). However, as Mann et al. point out, using exact computation libraries can result in a slowdown of over twenty times, creating a severe tension between accuracy and practical utility.

Filtered exact arithmetic resolves this tension by acting as a multi-stage pipeline. It exploits the fact that for the vast majority of geometric queries, the points are far enough apart that floating-point arithmetic yields the correct sign. The pipeline operates as follows:

  1. The Floating-Point Filter: The algorithm evaluates the predicate using fast, standard floating-point arithmetic. Crucially, it also computes a conservative error bound ($\epsilon$) for that specific calculation based on the magnitude of the inputs.
  2. The Certainty Test: If the absolute value of the floating-point result is strictly greater than $\epsilon$, the sign is guaranteed to be correct. The result is accepted immediately, maintaining standard hardware speeds.
  3. The Exact Fallback: If the result falls within the $[-\epsilon, \epsilon]$ error margin, the numerical outcome is uncertain. The system then—and only then—switches to an expensive exact arithmetic kernel to resolve the true sign.

Dey et al. demonstrate that this filtered approach eliminates catastrophic failures like infinite loops while maintaining performance levels comparable to standard floating-point implementations.

[Input Coordinates]
        │
        ▼
┌──────────────────────────────┐
│  Fast Floating-Point Filter  │ ──► Computes value & error bound (ε)
└──────────────────────────────┘
        │
        ├─► Is |value| > ε? ───YES───► [Guaranteed Correct Sign] (Fast Path)
        │
        ▼ NO (Uncertain Region)
┌──────────────────────────────┐
│   Exact Arithmetic Kernel    │ ──► [Guaranteed Correct Sign] (Slow Path)
└──────────────────────────────┘

Adaptive Precision and Algebraic Primitives

When geometric problems involve non-linear boundaries, such as circular arcs or quadric surfaces, predicates require evaluating algebraic roots rather than simple polynomial determinants.

To handle these complex cases efficiently, Krishnan et al. introduced the PRECISE library, which extends the filtering concept using range arithmetic and iterative precision refinement. Instead of jumping straight to full arbitrary precision when a filter fails, the system progressively increases the bit-precision of the calculation until the ambiguity is resolved.

A complementary approach scales precision based on spatial context. In geometric subdivision algorithms, Cucker et al. showed that certified topological correctness can be achieved by dynamically scaling the bit-precision of floating-point arithmetic relative to the local scale of the subdivision cells. As cells get smaller and features become more crowded, the arithmetic precision automatically deepens to prevent rounding errors from corrupting the topology.

Bypassing Floats Entirely

In some domains, researchers avoid the complexities of floating-point filters by restructuring the problem to use purely discrete or rational representations.

Exact Rational Arithmetic

For interactive applications like geometric constraint solvers, cumulative rounding errors from repeated user manipulations can cause parallel lines to drift or constraints to break. Allen et al. demonstrated that utilizing exact rational arithmetic instead of floating-point representations prevents this drift entirely, ensuring that topological properties and constraints remain perfectly consistent over indefinite iterations.

Integer and Combinatorial Mappings

When transformations involve trigonometric functions (such as rotating a digital image), the resulting coordinates are inherently irrational. To eliminate floating-point precision errors during these events, Ngo et al. leveraged periodic continued fractions and exact integer arithmetic. This allows algorithms to sort and process critical intersection events using the algebraic properties of quadratic irrationals, bypassing numerical approximation entirely.

Low-Degree Predicates

Another design strategy is to simplify the mathematical complexity of the predicates themselves. Nielsen et al. showed that by redesigning algorithms to rely exclusively on low-degree algebraic predicates (such as simple squared distance comparisons), developers can completely avoid complex solvers and implement robust geometric software using basic integer arithmetic.

Key Foundational Work

Epsilon Geometry: Building Robust Algorithms from Imprecise Computations (1989) — contributed 5 concept elements to this direction.
Using Computer Design and Simulation to Improve Manufacturing Productivity (1992) — contributed 2 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 89 papers
  2. Version 1 · 2026-10-04 · 87 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_robust_geometric_computation_d289143b,
  title = {robust geometric computation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/robust-geometric-computation/rdr_d289143b66a84e8cba71c94a086da73d},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 2, frozen text):

@misc{lacuna_robust_geometric_computation_d289143b_v2,
  title = {robust geometric computation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/robust-geometric-computation/rdr_d289143b66a84e8cba71c94a086da73d/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake