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.

  1. 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.
  2. 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.
  3. 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.
  4. 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.