2006 | OriginalPaper | Chapter
Backward Error Analysis in Computational Geometry
Authors : Di Jiang, Neil F. Stewart
Published in: Computational Science and Its Applications - ICCSA 2006
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
A recent paper, published in Algorithms—ESA2004, presented examples designed to illustrate that using floating-point arithmetic in algorithms for computational geometry may cause implementations to fail. The stated purpose was to demonstrate, to students and implementors, the inadequacy of floating-point arithmetic for geometric computations. The examples presented were both useful and insightful, but certain of the accompanying remarks were misleading. One such remark is that researchers in numerical analysis may believe that simple approaches are available to overcome the problems of finite-precision arithmetic. Another is the reference, as a general statement, to the inadequacy of floating-point arithmetic for geometric computations.
In this paper it will be shown how the now-classical backward error analysis can be applied in the area of computational geometry. This analysis is relevant in the context of uncertain data, which may well be the practical context for computational-geometry algorithms such as, say, those for computing convex hulls. The exposition will illustrate the fact that the backward error analysis does not pretend to overcome the problem of finite precision: it merely provides a tool to distinguish, in a fairly routine way, those algorithms that overcome the problem
to whatever extent it is possible to do so.
It will also be shown, by using one of the examples of failure presented in the principal reference, that often the situation in computational geometry is exactly parallel to other areas, such as the numerical solution of linear equations, or the algebraic eigenvalue problem. Indeed, the example mentioned can be viewed simply as an example of an unstable algorithm, for a problem for which computational geometry has already discovered provably stable algorithms.