Ioannis Z. Emiris

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-91-642
July 1991

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1991/CSD-91-642.pdf

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.

BibTeX citation:

@techreport{Emiris:CSD-91-642,
    Author = {Emiris, Ioannis Z.},
    Title = {An Efficient Approach to Removing Geometric Degeneracies},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1991},
    Month = {Jul},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1991/6390.html},
    Number = {UCB/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 <i>d</i>^2+alpha, where <i>d</i> 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.}
}

EndNote citation:

%0 Report
%A Emiris, Ioannis Z.
%T An Efficient Approach to Removing Geometric Degeneracies
%I EECS Department, University of California, Berkeley
%D 1991
%@ UCB/CSD-91-642
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1991/6390.html
%F Emiris:CSD-91-642