Understanding the symbolic perturbation adopted in CGAL
I am studying a paper by CGAL authors describing their approach to symbolic perturbation technique. This approach has been used in Delaunay_triangulation_3 class to be able to compute unique Delaunay triangulation even in the presence of degneracies in the input. So, before starting my discussion on CGAL solution to degenerate point configuration I will discuss the problem itself.
Lets consider the problem in more convenient 3D space. The problem can be formulated as: Given a set of points with atleast one 5-point set in cospherical arrangement(the degenerate condition), we need to find a unique Delaunay triangulation of the point set. Now why this problem is a problem is because as per definition of Delaunay triangulation the circumsphere of every tetrahedron will not have any input point inside on it. But since we already have 5 cospherical points, it allows for two possible triangulations of these 5 points and hence the input. So the challenge lies in avoiding this ambiguity and coming up with a unique triangulation still.
Natually, it seems that if we change the input points so that cospherical condition is broken this ambiguity will not appear, but it raises another question as to how to determine the perturbation/modification of the points?
It was proposed by Edlesbrunner to instead perturb the points symbolically. It in essence means to change the problem definition itself, but it is changed in a way such that it converges to the original problem in limiting cases as we will see later in our discussion of the CGAL paper.
Now, lets come back to the approach proposed and implemented by CGAL guys. They have described their approach in a report here. Although that paper is about retetrahedralization of cavity created by vertex removal to support dynamic insertion and removal in Delaunay triangulation, I will keep my discussion limited to how they deal with the degenerate input. Specifically, they have proposed an approach to symbolically perturb the input so as to prevent insphere predicate from returning 0 so as to be able to select a unique Delaunay triangulation in face of degenerate input. Before I jump into the acutal details of implementation of symbolic perturbation in CGAL let me explain what insphere predicate observes.
Here is an example MathJax inline rendering \( x^{2}\).
Lets jump to their treatment of insphere now,
TODO