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

ABSTRACT

This paper describes a general-purpose programming technique, called Simulation of Simplicity, that can be used to cope with degenerate input data for geometric algorithms. It relieves the programmer from the task of providing 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 that do not use it. We believe that this technique will become a standard tool in writing geometric software.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: AURENHAMMER, F., AND IMAI, H. Geometric relations among voronoi diagrams. Tech. Rep. 228, Institute ffir Informationsverarbeitung, Technische Universitiit Graz, Austria, 1986.
• 3: CHARNES, A. Optimality and degeneracy in linear programming. Econometrica 20, 2 (April 1952), 160-170.
• 4: CHV~,TAL, V. Linear Programming. Freeman, San Francisco, Calif., 1983.
• 5: CHVikTAL, V., AND KLINCSEK, G. Finding largest convex subsets. In Proceedings of the 11th Southeastern Conference on Combinatorics, Graph Theory and Computing. 1980, pp. 453-460.
• 6: DANTZIG, G.B. Linear Programming and Extensions. Princeton University Press, Princeton~ N.J., 1963.
• 7: DANTZIG, G. B., ORDEN, A., AND WOLFE, P. The generalized simplex method for minimizing a linear form under linear inequality restrictions. Pac. J. Math. 5, 2 (June 1955), 183-195.
• 8: H. Edelsbrunner, Edge-skeletons in arrangements with applications, Algorithmica, v.1 n.1, p.93-109, Jan. 1986 [doi>10.1007/BF01840438]
• 9: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• 10: 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]
• 11: 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]
• 12: FORREST, A.R. Computational geometry in practice. In Fundamental Algorithms for Computer Graphics, E. A. Earnshaw, Ed. Springer-Verlag, Berlin, West Germany, 1985, pp. 707-724.
• 13: GOLUB, G. H., AND VAN LOAN, C.F. Matrix Computations. Johns Hopkins University Press, Baltimore, Md., 1983.
• 14: GOODMAN, J. E., AND POLLACK, R. Multidimensional sorting. SIAM J. Comput. 12, 3 (Aug. 1983), 484-507.
• 15: 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]
• 16: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 17: MOCKE, E.P. SoS--A first implementation. Master's thesis, Department of Computer Science, Univ. of Illinois at Urbana-Champaign, Urbana, Ill., Sept. 1988.
• 18: 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]
• 19: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 20: Raimund Seidel, A Convex Hull Algorithm Optimal for Point Sets in Even Dimensions, University of British Columbia, Vancouver, BC, Canada, 1981
• 21: SEIDEL, R. On the size of closest-point Voronoi diagrams. Tech. Rep. F94, Institute fur Informationsverarbeitung, Technische Universitat Graz, Austria, 1982.
• 22: 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]
• 23: YAP, C.K. Symbolic treatment of geometric degeneracies. In Proceedings of the 13th IFIP Conference on System Modeling and Optimization (Chuo Univ., Tokyo, Aug. 31-Sept. 4), 1987.
• 24: 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.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

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

  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Reliability and robustness

General Terms:
Algorithms, Reliability