ACM/NSF Strategic Directions in Computing Research
Steven Fortune
Geometric algorithms are usually described in the conceptual model
of the real numbers, with unit-cost exact arithmetic operations.
Implementers often substitute floating-point arithmetic for real
arithmetic.
This leads to the well-known problem of numerical robustness,
since geometric predicates depend upon sign-evaluation, which
is unreliable if expression evaluation is approximate.
An ideal solution to the problem of numerical robustness would be
simple, efficient, and widely applicable.
No such solution exists or is likely to exist.
Exact evaluation of geometric predicates is the most promising
approach to numerical robustness.
Performance is an obvious concern, since the required arithmetic
precision exceeds the native precision of computer hardware,
necessitating the use of software extended-precision arithmetic.
There is considerable evidence that adaptive-precision arithmetic,
if engineered carefully, can substantially reduce the effective cost of extended-precision
evaluation.
Performance comparable to floating-point arithmetic has been achieved
for algorithms with relatively modest precision requirements, e.g.
evaluating simple predicates on
points, lines, and planes in
dimensions two and three.
Research in the following topics could make exact evaluation more widely applicable.
- Rounding algorithms.
A geometric object such as a polyhedron has both geometric coordinates and combinatorial
structure.
Virtually any time a new object is computed exactly, coordinate bit-length increases.
Often an application is satisfied with a low-precision approximation to the
answer, as long as the combinatorial and geometric information are consistent.
However, rounding the coordinates of complicated object like a polyhedron is not straightforward,
since incidence information may be invalidated by small perturbations of faces and vertices.
- Software exact arithmetic.
Ideally, software extended- or adaptive-precision arithmetic would be as convenient
and flexible as native hardware arithmetic, and nearly as efficient.
No current design achieves all these goals, and perhaps none can,
but there are plenty of points in the design space to explore.
- Algebraic curves and surfaces.
Algebraic techniques such as resultants and Sturm sequences can be used to implement
exact geometric primitives on algebraic curves and surfaces. Naive estimates
of the required arithmetic bit-length are daunting. There is considerable
room for improvement both in the underlying theory and in adaptive-precision
evaluation of predicates.
- Methodology.
A complex application might have a kernel that requires complete robustness,
hence requires exact evaluation, and an outer layer that can tolerate imprecision, hence
can tolerate floating-point evaluation.
Separating the two parts, and in particular designing the kernel to have minimal
arithmetic requirements, may be a considerable engineering challenge.
Documented examples of the separation would be a valuable reference.