Re:CGAL: Computational Geometry Algorithms Library
by vladf on Thursday December 01, 2022 @05:20PM
(#33823776)
Thank you for the detailed reply. "Classroom examples of robustness problems in geometric computations" is great; I look forward to doing a deep read there.
Your reference, "The Nature and Meaning of Perturbations in Geometric Computing" itself refers to "On degeneracy in geometric computations" (https://dl.acm.org/doi/10.5555/314464.314474) which I think points to a less tame reality where the answer to my question (continuity claims about CG outputs) is "it depends on the CG problem".
Most predicates boil down to a decision of whether some quantity is less than, equal, or greater than zero. CGAL implements filtered predicates — a work of art in my opinion — where they use ordinary computation and if the result is far enough away from zero, return its sign. If not, they switch to higher precision or interval arithmetic. A good explanation of how this works (what "far enough from zero" actually means) is in O. Devillers and S. Pion, “Efficient Exact Geometric Predicates for Delaunay Triangulations,” in Proceedings of the 5th Workshop on Algorithm Engineering and Experiments, pp. 37–44, 2003.
The larger problem of symbolically perturbing input, so that it's in general position (in a sense, what to do if your predicate returns 0) was a very active research topic in the 90s, and both the problem and much of the work is explained really well in R. Seidel, “The Nature and Meaning of Perturbations in Geometric Computing,” Discrete Comput. Geom., vol. 19, no. 1, pp. 1–17, 1998.