We introduce the numerical non-robustness phenomenon and prescribe our Exact Geometric Computation (EGC) Solution. Finally, we discuss current research which extends the EGC to a softer version with much wider applicability.
Motivation: Numerical Non-Robustness
Solution: The Exact Geometric Computation Approach
Geometric computation always involve some geometric structure D, whether we are constructing D or implicitly searching in it. By its nature, D has a combinatorial (or, topological) part and a numerical part, and these two parts together must satisfy suitable consistency relation. The approach to robustness called Exact Geometric Computation (EGC) says that nonrobustness is caused by geometric inconsistency, and the best way to ensure consistency is to compute the combinatorial part exactly.
To achieve the goals of EGC, we must first recognize that the combinatorial part is often defined by the numerical part. In an algorithm, we navigate or construct the combinatorial by performing tests. Such tests amount to evaluating the sign of real predicates (typically polynomial functions), leading to a two-way or three-way branching in the program. A typical test is evaluating the sign of a determinant. If we ensure that such tests are error-free, then the resulting structure would be exact.
So the exactness in EGC is in the "geometry'', not in the arithmetic. In contrast to "exact'' arithmetic approaches, only "sufficiently accurate'' arithmetic is needed. This simple fact has profound implications. In what we call the EGC mode of computation, we have to answer the question -- how much precision is sufficient? Many research issues in EGC amounts to answering this question efficiently. More importantly, from a practical viewpoint, we can encode the EGC solution in a software library. This means that any programmer can achieve completely robust algorithms just by calling such a library! The first such system is our Real/Expr Package. Currently, there are two such EGC libraries: LEDA_real and our Core Library. The major European software library efforts, CGAL and LEDA are also committed to this EGC approach.
Current Research: Beyond EGC
Since around 2009, we have been interested in going beyond EGC. We are still interested in ``exactness'' but allowing prescribed relaxation. For example, one such concept is the notion of ``resolution-exactness''. Suppose we now introduce a new resolution parameter, ε > 0. Intuitively, it means that we want to compute the solution up to ε accuracy. But the combinatorial nature of the output might be affected by this ε. This can be viewed as a generalization of EGC because when ε = 0, we again have EGC. But in practice, there is a vast difference between ε = 0 and ε > 0. In particular, we can avoid algebraic computation altogether when ε > 0 --- provided we formulate the notion of resolution-exactness ``correctly'' (we must not ''smuggle'' in exactness even with the ε). We have successfully applied this notion to well-known problems in robotics, computational geometry and algebraic computation. Specifically, in motion planning, root isolation, curve and surface analysis and differential equations. Such algorithms are essentially numerical in nature, and the key lies in interval methods and their generalizations. Ultimately, going beyond EGC is essential because for many reasons: