Structural filtering: a paradigm for efficient and exact geometric programs (Q2486081)

The authors introduce a structural filtering technique, which can be used for the exact implementation of incremental algorithms of computational geometry. Structural filtering considers the execution of an algorithm as a sequence of steps and is applied to the search step of geometric algorithm. Structural filtering uses the structure of the search tree to improve the running time of the algorithm. The authors investigate the possibility of structural filtering implementation theoretically as well as experimentally. They give an overview of filtering techniques and strategies and discuss the advantages and disadvantages of predicate filtering and structural filtering approaches. The methods of searching and sorting are mentioned, too. This article is an extension of their previous paper with the same title, which has been published in the Proceeding sof the 11th Canadian Conference on Computational Geometry, Vancouver, Canada, 1999.