Degeneracy in Geometric Computation and the Perturbation Approach

We study to problem of degeneracy in geometric algorithms and show that degeneracies arise even in simple Euclidean constructions with ruler and compass. We distinguish between problem-dependent and algorithm-dependent degeneracies, and argue that the popular perturbation approach is suitable for removing only the latter but not the former. Examples demonstrate the dangers of removing problem-dependent degeneracies using the perturbation approach and we identify circumstances where this method is justified. We propose to deal with degeneracies by giving precise input-output specifications of the geometrics problem under consideration and by handling problem-dependent degenerate cases individually right from the beginning of algorithm construction. Algorithm-dependent degeneracies are removed using perturbation or its simplest version, lexicographic ordering. As an example of this approach we present an algorithm for the computation of the winding number which yields provably correct results when implemented in integer and floating point arithmeti