Franco P. Preparata
Brown University
Issues of robustness have become central to the development of geometric algorithms in recent years. The original assumption of a computational model obtained by extending the traditional RAM to real-number arithmetic proved less innocent than originally thought. To equate floating-point arithmetic to real-number arithmetic turned out to be indefensible on the basis of failures in practical applications. Another convenient assumption has been the hypothesis of "general position," which dispenses with the detailed consideration of special cases. Unfortunately, degenerate conditions (colinearity, cocircularity) which are likely to be generated by coarse-grid data as they occur in practice, give rise to numerically critical events. Failures originating from these assumptions have fundamentally hindered the adoption of computational geometry by practitioners.
Over the years several approaches have been proposed to remedy these shortcomings. An excellent and succint survey of the underlying philosophies is represented by the introductory note prepared as a platform for this discussion by Steven Fortune (see also by Steven Fortune, "Computational geometry: perspectives and challenges," B. Chazelle, editor). It is likely that no single approach may be capable of conferring robustness to geometric algorithms. Presumably, several tools may be included in an arsenal designed to achieve robust computations.
However, an approach that has the potential to yield a useful methodology is the following. The numerical computations of a geometric algorithm are basically of two types, which we may designate as "tests" and "constructions". These two types have clearly distinct roles. Tests are associated with branching decisions in the algorithm that determine the flow of control, whereas constructions are used to produce the objects that normally represent the output of the application.
Approximations in the execution of the constructions give rise to approximate results, which may nevertheless be entirely acceptable as long as the maximum error does not exceed the resolution required by the application (in all cases, some more or less coarse grid). On the other hand, approximations in the execution of tests may produce incorrect branchings, which may have catastrophic consequences, since they may yield structurally (i.e., topologically) incorrect results (such as a missed intersection or an open polygon). Therefore, tests have much more stringent requirements, which leads to the conclusion that they must be carried out with complete accuracy, whereas some tolerance is permitted for constructions. (It must be observed, however, that such tolerance should not lead to contradict the topological structure of the result as provided by the tests.)
Complete accuracy seems to revert us back to the infinite precision implied by real-number arithmetic. Fortunately, the inherently coarse nature of the input data comes to the rescue in this connection. Each predicate is expressible as the sign of a multivariate polynomial in the input variables. If input variables are assumed of degree 1, the degree of such polynomial specifies the maximum precision required by the test in question. Of course, only in near-degenerate cases the maximum precision may have to be deployed. In typical cases, much lower precision may be sufficient to confidently evaluate the predicate. It is therefore the function of an "arithmetic filter" to identify the adequate precision. In this framework, the development of cost/effective filters may be one of the major challenges in the quest for robustness.
Robustness in Geometric Algorithms
This document was generated using the LaTeX2HTML translator Version 95 (Thu Jan 19 1995) Copyright © 1993, 1994, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
The command line arguments were:
latex2html -split 0 preparata.tex.
The translation was initiated by Roberto Tamassia on Fri May 10 22:05:57 EDT 1996