An Efficient Approach to Removing Geometric Degeneracies
Emiris, Ioannis Z.
Technical Report Identifier: CSD-91-642
Abstract: We wish to increase the power of an arbitrary geometric algorithm designed for non-degenerate input, by allowing it to execute over arbitrary inputs. This paper describes a deterministic direct perturbation of the input which applies to algorithms whose branching decisions depend on determinants in the input parameters. We concentrate on four predicates that cover most important algorithms in computational geometry. The method alters the input parameters by infinitesimal amounts to guarantee that the perturbed input lies in general position. It is an attractive candidate for practical use, and is considerably simpler as well as more efficient than existing approaches. Specifically, it is the first method with a complexity overhead that is polynomial in the input size and, in most cases, a small constant. Under our real computation model, the asymptotic complexity remains unaffected; the bit complexity is at worst increased by a factor proportional to d^2+alpha, where d is the dimension of the geometric space of the input objects and alpha an arbitrarily small positive constant. A variation of the perturbation, applied to two predicates, achieves optimal bit size for the perturbation quantities and is even more efficient. Lastly, we illustrate the applicability of our approach.