We first describe the numerical non-robustness phenomenon, then prescribe the Exact Geometric Computation (EGC) Solution. Finally, we discuss current research for moving beyond EGC.
Motivation: Numerial Non-Robustness
Solution: The Exact Geometric Computation Approach
Geometric computation always involvse 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, Epsilon>0. Intuitively, it means that we want to compute the solution up to Epsilon accuracy. But the combinatorial nature of the output might be affected by this Epsilon. This can be viewed as a generalization of EGC because when Epsilon = 0, we again have EGC. But in practice, there is a vast difference between Epsilon=0 and Epsilon>0. In particular, we can avoid algebraic computation altogether when Epsilon>0 --- provided we formulate the notion of resolution-exactness correctly. We have been applying this notion to problems such as motion planning, classical problems of computational geometry, for problems related to root isolation, curve and surface analysis, etc. Such algorithms are essentially numerical in nature. Ultimately, going beyond EGC is essential because there are many problems for which the EGC solution is too expensive, the EGC notion is not realistic or no EGC solutions are known. The last case encompass most transcendental problems.