Degeneracies arise from the special position of two geometric objects. For example, two segments in general position either do not intersect or intersect at a point interior to both segments. Two intersecting segments in special position may overlap, may share a common endpoint with or without being collinear, may have one segment endpoint interior to the other segment, etc. Real-world data is likely to be degenerate. For example segment endpoints may be explicitly chosen from a coarse grid, to facilitate interactive design.
The effect of degeneracy is to vastly increase the number of special cases. While a sorting algorithm must deal only with the possibility of two keys being equal, a typical geometric algorithm faces the possibility of dozens or hundreds of different special cases [148][71][49][47]. The presence of numerical data, added to the inherent complexity of geometric data types, makes geometric algorithms much harder to implement correctly than combinatorial (say, graph-theoretical) ones. They are also much harder than just purely numerical algorithms (such as those addressed by numerical analysis) many of which consist of large chunks of straight-line code. Since the overall utility of an implementation may depend upon the correct treatment of special cases, the handling of special cases can permeate the implementation. This raises the obvious reliability concern that all cases have been considered and correctly handled.
Symbolic perturbation schemes allow degeneracies to be resolved automatically.
Conceptually, each geometric coordinate is replaced with a symbolically
perturbed coordinate
, where
is unknown
but very small and the perturbation function
is simple, say a polynomial.
Substitution of the symbolically
perturbed coordinates in a predicate expression results
in a polynomial in
with coefficients determined
by the original geometric coordinates.
The sign of the expression is given by the sign of the first
nonzero coefficient, with coefficients taken in order of increasing powers
of
.
For many classes of predicates, the
can be chosen
to resolve all degeneracies.
While symbolic perturbation is certainly a useful tool in the implementation of geometric algorithms, existing schemes are not as applicable as might be desired. First, symbolic perturbation requires exact arithmetic, since the correctness of the perturbation depends upon exact evaluation of arithmetic expressions. Second, symbolic perturbation has been worked out in detail for only a small class of predicates. For example, constructed objects are often disallowed, since the perturbation function for a constructed object depends upon how the object was constructed and is much more complicated than the perturbation function for a primitive object. Perhaps most fundamentally, in a degenerate situation an algorithm implemented using symbolic perturbation does not solve the problem instance, but an arbitrarily-chosen nearby problem instance. This might be inappropriate in some applications. For example, a highly degenerate polytope may see its combinatorial complexity blow up exponentially as a result of a small perturbation.
Although much work remains to make symbolic perturbation generally useful, no other approach to the issue of degeneracy has as much promise.