An efficient approach to removing geometric degeneracies

ABSTRACT

Our aim is to perturb the input so that an algorithm designed under the hypothesis of input non-degeneracy can execute on arbitrary instances. The deterministic scheme of [EmCa] was the first efficient method and was applied to two important predicates. Here it is extended in a consistent manner to another two common predicates, thus making it valid for most algorithms in computational geometry. It is shown that this scheme incurs no extra algebraic complexity over the original algorithm while it increases the bit complexity by a factor roughly proportional to the dimension of the geometric space. The second contribution of this paper is a variant scheme for a restricted class of algorithms that is asymptotically optimal with respect to the algebraic as well as the bit complexity. Both methods are simple to implement and require no symbolic computation. They also conform to certain criteria ensuring that the solution to the original input can be restored from the output on the perturbed input. This is immediate when the input to solution mapping obeys a continuity property and requires some case-specific work otherwise. Finally we discuss extensions and limitations to our approach.

REFERENCES

• AHU: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• Ca: John F. Canny, Computing Roadmaps of General Semi-Algebraic Sets, Proceedings of the 9th International Symposium, on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.94-107, October 07-11, 1991
• CoLo: George E. Collins , Rudiger Loos, Real zeroes of polynomials, Computer algebra: symbolic and algebraic computation (2nd ed.), Springer-Verlag New York, Inc., New York, NY, 1983
• Da: Dantzig G.B., Linear Programming and Extensions, Princeton University Press, Princeton, 1963.
• Do: Dobrindt K., Algorithmen fiir Polyeder, Master's thesis (in German), Fachbereich Informatik, Universitiit Saarbriicken, Germany, May 1990.
• Ed: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• EdGu: H Edelsbrunner , L J Guibas, Topologically sweeping an arrangement, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.389-403, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12171]
• EdMu: Herbert Edelsbrunner , Ernst Peter Mücke, Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms, ACM Transactions on Graphics (TOG), v.9 n.1, p.66-104, Jan. 1990 [doi>10.1145/77635.77639]
• EdWa: H. Edelsbrunner , R. Waupotitsch, Computing a ham-sandwich cut in two dimensions, Journal of Symbolic Computation, v.2 n.2, p.171-178, June 1986 [doi>10.1006/jsco.1998.0247]
• Em: Emiris I., An Efficient Approach to Removing Geometric Degeneracies, Master's thesis, Computer Science Division, UC Berkeley, May 1991.
• EmCa: Ioannis Emiris , John Canny, A general approach to removing degeneracies, Proceedings of the 32nd annual symposium on Foundations of computer science, p.405-413, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185399]
• KG: Walter Keller-Gehrig, Fast algorithms for the characteristic polynomial, Theoretical Computer Science, v.36 n.2-3, p.309-317, June 1985
• PrSh: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• Se: Seidel R., private communication, 1991.
• Ya87: Yap C.-K., Symbolic treatment of geometric degeneracies, Proc. 13th IFIP Conf. on $ys. Modehng and Optimizatzon, Tokyo, pp. 348- 358, 1987.
• Ya88: C. K. Yap, A geometric consistency theorem for a symbolic perturbation scheme, Proceedings of the fourth annual symposium on Computational geometry, p.134-142, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73407]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

General Terms:
Algorithms, Theory