Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms

ABSTRACT

This paper describes a general purpose programming technique, called the Simulation of Simplicity, which can be used to cope with degenerate input data for geometric algorithms. It relieves the programmer from the task to provide a consistent treatment for every single special case that can occur. The programs that use the technique tend to be considerably smaller and more robust than those obtained without using it. We believe that this technique will become a standard tool in writing geometric software.

REFERENCES

• AHU74: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• AI86: F. Aurenhammer and H. Imai. Geometric relations among Voronoi diagrams. Technical Report 228, Institute fiir Informationsverarbeitung, Technische Universit~it Graz, Austria, 1986.
• Cha52: A. Charnes. Optimality and degeneracy in linear programming. Econometrica, 20(2):160-170, 1952.
• Chv83: V. Chv~tal. Linear Programming. W. H. Freeman and Company, New York, 1983.
• CK80: V. Chv~tal and G. Klincsek. Finding largest convex subsets. In Proceedings 11-th Southeastern Conference on Combinatorics, Graph Theory and Computing, pages 453-460, 1980.
• Dan63: G.B. Dantzig. Linear Programming and Eztensions. Princeton University Press, Princeton, New Jersey, 1963.
• DOW55: G. B. Dantzig, A. Orden, and P. Wolfe. The generalized simplex method for minimizing a linear form under linear inequality restrictions. Pacific Journal of Mathematics, 5:183-195, 1955.
• Ede86: H. Edelsbrunner, Edge-skeletons in arrangements with applications, Algorithmica, v.1 n.1, p.93-109, Jan. 1986 [doi>10.1007/BF01840438]
• Ede87: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• EG86: 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]
• EW86: 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]
• For85: A.R. Forrest. Computational geometry in practice. In E. A. Earnshaw, editor, Fundamental Algorithms for Computer Graphics, pages 707-724, Springer Verlag, Berlin, Heidelberg, Germany, 1985.
• GP83: J.E. Goodman and R. Pollack. Multidimensional sorting. SIAM Journal on Computing, 12:484-507, 1983.
• GS85: Leonidas Guibas , Jorge Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics (TOG), v.4 n.2, p.74-123, April 1985 [doi>10.1145/282918.282923]
• GVL83: G.H. Golub and Ch. F. Van Loan. Matriz Computations. The John Hopkins University Press, Baltimore, Maryland, 1983.
• Knu69: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• Muc85: E.P. Miicke. Ein Modell zur Elimination degenerletter FKlle in geometrischen Algorithmen. Graduating thesis, Institute fiir Informationsverarbeitung Technische Universit~it Graz, Austria, 1985.
• PH77: F. P. Preparata , S. J. Hong, Convex hulls of finite sets of points in two and three dimensions, Communications of the ACM, v.20 n.2, p.87-93, Feb. 1977 [doi>10.1145/359423.359430]
• PS85: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• Sei81: Raimund Seidel, A Convex Hull Algorithm Optimal for Point Sets in Even Dimensions, University of British Columbia, Vancouver, BC, Canada, 1981
• Sei82: R. Seidel. On the size of closest-point Voronoi diagrams. Technical Report F94, Institute fiir Informationsverarbeitung, Technische Universit,it Graz, Austria, 1982.
• Sei86: R Seidel, Constructing higher-dimensional convex hulls at logarithmic cost per face, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.404-413, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12172]
• Yap87: Chee Keng Yap. Symbolic treatment of geometric degeneracies. In Proceedings l$-th 1FIP Conference on System Modelling and Optimization, Chuo University, Tokyo, 1987.
• Yap88: 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:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
        D.2.10 Design**
            Subjects: Methodologies**

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

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms
      I.1.3 Languages and Systems
          Subjects: Evaluation strategies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations; Geometric algorithms, languages, and systems; Modeling packages
  I.5 PATTERN RECOGNITION
  I.6 SIMULATION AND MODELING

General Terms:
Algorithms, Design, Measurement, Theory