Technical Report No. 8, December 1987 - Abstract

Thomas Ottmann, Gerald Thiemt, Christian Ullrich:
On Arithmetical Problems of Geometric Algorithms in the Plane

This report is not available in electronic form!

In the last years computational geometry has achieved a mature status within the framework of algorithms and data structures. Hundreds of new solutions for geometric problems are available now. Corresponding algorithms are distinguished by clever data structures, rigorous proofs and nontrivial complexity analysis.

The application of the new algorithms in real systems is less successful. One of the reasons for this phenomenon is given by the numerical problems occuring during execution of nearly all geometric algorithms.

This paper gives an introduction to the latter class of problems in geometric algorithms. The scan-line algorithm for computing all pairs of intersecting line segments in the plane serves as model example for the isolation of basic operations which have to be handled numerically correct. It can be shown that the optimal evaluation of arithmetic expressions provides a solid tool for the solutions of the problems.