The investigators will develop an approximate computational geometry that is algorithm independent, accurate, and fast. Geometric predicate evaluation and element construction will be performed approximately using floating point arithmetic. Degeneracy will be handled transparently. The evaluation and construction techniques will be encapsulated in a software library that will be free for nonprofit use.
The research challenge is robustness: the output of an approximate algorithm must be correct for a small perturbation of the given input. This definition extends the numerical analysis definition of a stable algorithm to cover combinatorial error. Robustness is a fundamental computer science problem that is a major challenge in computational geometry. The predominant strategy in computational geometry, exact computation using algebraic geometry, has high computational complexity and contradicts the standard scientific and engineering strategy of approximate computation with error bounds. The investigators will adapt approximate computation to the special needs of computational geometry, which is primarily combinatorial. This task involves core research at the interface between computational geometry and numerical computing.
Robust approximate computation will transform how computational geometry is taught, how algorithms are developed and implemented, and how the field interacts with the wider scientific and engineering community. Introductory courses will present a rigorous, practical robustness theory, instead of treating robustness in an ad hoc, incomplete way. Programmers will implement real RAM algorithms as stated, using our library to ensure robustness and to handle degeneracy, instead of addressing these problems anew for every algorithm, which is often a major research challenge. Computational geometry will be available to other disciplines in the form of high-quality software libraries, akin to modern applied mathematics libraries.
Computational geometry is the branch of computer science that develops algorithms for solving geometry problems. The field addresses abstract problems, such as how a set of lines partitions the plane into regions and how a polyhedron can be decomposed into tetrahedrons. Algorithms that solve these problems advance our understanding of the interplay between computing and geometry. Many scientific and engineering problems can be formulated in the language of computational geometry. Examples include planning a safe path for a robot in a cluttered environment, computer-aided design of complex parts using a library of standard shape, and construction of three-dimensional models of tumors from MRI data. We researched the robustness problem: how to convert computational geometry algorithms into reliable, efficient software. Numerical algorithms, including algorithms of computational geometry, are formulated under the simplifying assumptions that real numbers have unit size and real arithmetic takes unit time. The is called the real-RAM model. However, algorithms are implemented using floating point computer arithmetic, which has rounding. The resulting program is accurate and its running time matches the prediction of the real-RAM model. Computational geometry algorithms are atypical because their control logic is expressed using predicates: polynomials whose signs are interpreted as truth values. Although floating point predicate evaluation is accurate, even a small error can make the sign incorrect and thus can cause a large error in the program output. Predicates can be evaluated exactly using integer arithmetic, but this strategy imposes a high overhead in running time and in computer memory. Moreover, a predicate can be degenerate, meaning zero rather than positive or negative. Degeneracy adds special cases to the control logic that are usually ignored by algorithm creators. The software must handle these cases or face erratic failures. We solved the robustness problem by developing a technique for evaluating predicates exactly and efficiently using floating point interval arithmetic. Interval arithmetic is a version of floating point arithmetic that computes an interval of floating point numbers, represented by its two endpoints, that is guaranteed to contain the exact result. We perturb the input parameters to the computational geomtry algorithm. The perturbation eliminates degeneracy by eliminating the coincidental relations among the inputs. We evaluate predicates in floating point interval arithmetic. The result is ambiguous if the interval contains zero, so either sign is consistent with this interval. We remove the ambiguity by increasing the precision of the interval arithmetic, which shrinks the interval. We adaptively increase the precision until the sign is verified. We use an extended precision software library called MPFR because the computer hardware does not directly support arbitrary precision arithmetic. We have proved that the expected overhead of this technique is constant for predicates in the input parameters. As a result of this work, we have been able to implement algorithms that were devised 25 years aga, but until now could not be turned into programs. Visit http://youtu.be/BsCcy0vYerw for a video illustrating an implementation of path planning.
