Robustness and Efficiency of Geometric Programs The Predicate Construction Kit (PCK).

@inproceedings{LévyGM2014,
 abstract = { In this paper, I focus on the robustness of geometric programs (e.g., Delaunay triangulation, Gocad’s “cut” algorithm, Voronoi-based meshing . . . ) w.r.t. numerical degeneracies. Some of these geometric programs require “exotic” predicates, not available in standard libraries (e.g., J.-R. Shewchuk’s implementation). I propose a complete methodology and a sample Open Source implementation of a toolset (PCK: Predicate Construction Kit) that makes it reasonably easy to design geometric programs free of numerical errors. The C++ code of the predicates is automatically generated from its formula, written in a simple specification language. Robustness is obtained through a combination of arithmetic filters, expansion arithmetics and symbolic perturbation.
As an example of my approach, I give the formulas and PCK source-code for the 4 predicates used to compute the intersection between a 3d Voronoi diagram and a tetrahedral mesh. This makes my Vorpaline algorithm robust to numerical errors, as well as the meshing methods developed on top of it (Romain Merland’s flow simulator, Jeanne Pellerin’s simplicial meshing and Arnaud Botella’s hex-dominant meshing algorithms). },
 author = { Levy, Bruno },
 booktitle = { Proc. 34th Gocad Meeting, Nancy },
 title = { Robustness and Efficiency of Geometric Programs The Predicate Construction Kit (PCK). },
 year = { 2014 }
}