Numerical Robustness · Computational Geometry · C++ / __int128

Predicates that cannot be wrong

Floating point silently corrupts geometric algorithms at exact ties and near-degeneracies, and nothing reports the failure when it happens. This repository proves the danger with committed adversarial inputs, proves the fix with exact arithmetic and an unbounded oracle, and guards the word "exact" with code, not prose.

View on GitHub Read the plain-language guide (PDF) Jump to results

657

committed adversarial cases: float wrong AND exact right, asserted case-by-case in CI

disagreements with an unbounded big-integer oracle across 1,554 re-verified cases

~2x

the measured cost of exactness (49.9 vs 27.5 ns orientation, x86-64), not orders of magnitude

The bug that started it

My D* Lite planner froze stale state into paths because two mathematically equal priority keys, computed along different arithmetic routes, landed one ulp apart in floating point, and a vertex the algorithm had to expand got buried behind one it didn't. The fix there was an exact integer cost metric. This repository generalizes that lesson into its own artifact: the classic geometric predicates (orientation, in-circle, segment intersection, and a convex hull built on them) implemented exactly over integer coordinates in __int128, with statically proven bounds.

First the danger has to be shown to be real. The committed corpus contains 657 adversarial inputs: Fibonacci triples whose true determinant is exactly ±1 at coordinate scale ~2⁵⁹ (Catalan's identity), near-collinear lattice quadruples whose in-circle determinant collapses into double's rounding noise, parallel segments separated by a determinant of exactly ±1. CI asserts, on every case, both that the naive double version gives the wrong answer and that the exact version gives the right one.

Bounds enforced by code, not prose

Exactness here has a domain: |coordinate| ≤ 2⁶⁰ for orientation, 2²⁸ for in-circle, proven by static bit-arithmetic. A documented bound that isn't checked would let an out-of-range input overflow silently and return a confidently wrong answer while the README still said "exact". So every predicate validates its inputs before any arithmetic happens, with a plain magnitude comparison that can never rely on observing the overflow it prevents, and throws on violation. The single most important test in the repository feeds coordinates one past each bound, in every argument position, and asserts the throw fires. For exact predicates over arbitrary doubles, the README names Shewchuk's adaptive predicates and CGAL: reimplementing those would risk looking right while being subtly wrong in the error-bound bookkeeping, the precise anti-pattern this project exists to refute.

The results

Log-log scatter: Fibonacci triples whose true determinant is exactly plus or minus one; double computes it correctly until coordinates reach about 2 to the 26, then returns zeros and garbage values — The vanishing determinant: every point's true determinant is exactly ±1, by construction. Double arithmetic sees it perfectly until the coordinates pass ~2²⁶, after which it returns zero or garbage in the 10¹⁵ range. Rendered from committed data that CI drift-checks against the committed generator.

Curve: percentage of near-collinear quadruples where the double in-circle sign is wrong, zero until scale 2 to the 24 and rising to about 7.5 percent at the bound — Where the bug class actually lives: on the near-collinear in-circle family, double is flawless up to coordinate scale ~2²⁴ and fails routinely near the bound. Mapping this matters: a corpus built at small scales would have "proven" a danger that doesn't exist there.

Two panels: counts of float-predicate hull invariant violations across 60 configs, and one config's exact residuals all sitting inside double's rounding-noise band — The same monotone-chain hull algorithm, two predicates, two truths: the float version violates convexity or containment on all 60 committed degenerate configs (left), because the ±1 residual structure that decides the hull sits entirely inside double's rounding-noise band (right). The exact hull, property-tested on random clouds as well, never violates an invariant.

An independent check: a Python big-integer oracle with no coordinate bound re-verifies every committed case (1,554 of them, zero disagreements) and computes answers beyond the C++ bound where the guard refuses, which shows the bound is a restriction of the implementation, not of the problem. CI also regenerates both the corpus and the figure data and diffs them against the committed files, so neither can drift from the code. The cost: exactness runs about 2x slower than the float versions (__int128 is cheap), measured and machine-named, because the float versions buy their speed by being wrong.