Structural Filtering -- A Paradigm for Efficient and Exact Geometric Programs

Stefan Funke, Kurt Mehlhorn, Stefan Naeher

We introduce a new and simple filtering technique that can be used in the implementation of geometric algorithms called "structural filtering". Using this filtering technique we gain about 20 % when compared to predicate-filtered implementations. Of theoretical interest are some results regarding the robustness of sorting algorithms against erroneous comparisons.

Prelim. version in Proc. 11th Canadian Conference on Computational Geometry (CCCG) 1999, Vancouver