Our Interpretation of Exact Computation|
Our Goal:
Robust geometric algorithms via Exact Computation |
Robust implementation of geometric algorithms is difficult to achieve. Many researchers have devised methods to address this problem within the framework of fixed-precision arithmetic. We believe that non-robustness of geometric algorithms is inherent when one is committed to fixed-precision, and the best general policy for attacking non-robustness is the ``exact computation''. |
|
|
|
| Geometric Structure = Combinatorial Structure + Numerical Quantities | We first clarify the nature of geometric computing. Geometric algorithms characteristically involve geometric structures which involves a combinatorial structure (such as a graph) with associated numerical quantities (such a numerical values labeling the nodes and edges). Moreover, there are consistency constraints governing the relation between the combinatorial structure and numerical quantities. This means that perturbing the numerical values without taking into account the combinatorial structure can lead to qualitatively different or inconsistent states, which may result in catastrophic errors in algorithms. Geometric algorithms may involve either the construction of, or searching in, geometric structures. |
|
|
|
| Exact Geometric Computation | Exact computation has a naive interpretation, namely, to compute every numerical quantity exactly. This surely guarantees the robustness of algorithms. But computing irrational numbers ``exactly'' needs suitable interpretation. Even in the rational case, it is too inefficient. We shall interpret exact geometric computing to mean computations in which numerical quantities are computed to sufficient precision so that the underlying combinatorial structure is mathematically exact. |
|
|
|
| Precision-driven Approach to Exact Implementation | We introduce the precision-driven approach to exact geometric computation. Assume the computation or algorithm amounts to the repeated evaluation of algebraic expressions. For each expression, we assume that some à priori bound of the necessary precision can be determined. For instance, if we often only need to know the sign of an expression, and amounts to approximating its value relative precision of 1-bit. This à priori precision can then be propagated to other parts of the computation, at run time, so that precision is locally adaptive. |
|
|
|
| Expr realizes Precision-Driven Computation |
As a tool for the above precision-driven approach to
exact geometric computation, we implement the Expr package for
the class of constructible real numbers, namely, real expressions over the operators
sqrt().
(i) the class BigFloat with automatic error-bound propagation, (ii) the extendible class Real that encompasses a variety of real number representations. |
|
|
|
| Use in Exact Geometric Computation | The Real/Expr package is sufficient for the exact implementation of most of algorithms in contemporary computational geometry. Real/Expr is useful for exact computation because many fundamental predicates of geometric algorithms can be represented by real constructible expressions. For example, "P is left of the directed line segment QR (directed from Q to R) is expressed as a sign of a suitable determinant constructed from P, Q, R. We construct the corresponding Real/Expr expression for this determinant and approximate its value to one relative bit of precision to get its (error-free) sign. |