Herbert Edelsbrunner
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.
- 1 AHO, A. V., HOPCROFT, J. E., AND ULLMAN, J.D. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Mass., 1974. Google Scholar
- 2 AURENHAMMER, F., AND IMAI, H. Geometric relations among voronoi diagrams. Tech. Rep. 228, Institute ffir Informationsverarbeitung, Technische Universitiit Graz, Austria, 1986.Google Scholar
- 3 CHARNES, A. Optimality and degeneracy in linear programming. Econometrica 20, 2 (April 1952), 160-170.Google Scholar
- 4 CHV~,TAL, V. Linear Programming. Freeman, San Francisco, Calif., 1983.Google Scholar
- 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.Google Scholar
- 6 DANTZIG, G.B. Linear Programming and Extensions. Princeton University Press, Princeton~ N.J., 1963.Google Scholar
- 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.Google Scholar
- 8 EDELSBRUNNER, H. Edge-skeletons in arrangements with applications. Algorithmica 1, 1 (1986), 93-109. Google Scholar
- 9 EDELSBRUNNER, H. Algorithms in Combinatorial Geometry. Springer-Verlag, Heidelberg, West Germany, 1987. Google Scholar
- 10 EDELSBRUNNER, H., AND GUIBAS, L.J. Topologically sweeping an arrangement. In Proceedings of the 18th Annual ACM Symposium on Theory of Computation. 1986, pp. 389-403. Google Scholar
- 11 EDELSBRUNNER, H., AND WAUPOTITSCH, R. Computing a ham-sandwich cut in two dimensions. J. Symbolic Comput. 2, 2 (June 1986), 171-178. Google Scholar
- 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.Google Scholar
- 13 GOLUB, G. H., AND VAN LOAN, C.F. Matrix Computations. Johns Hopkins University Press, Baltimore, Md., 1983.Google Scholar
- 14 GOODMAN, J. E., AND POLLACK, R. Multidimensional sorting. SIAM J. Comput. 12, 3 (Aug. 1983), 484-507.Google Scholar
- 15 GUIBAS, L. J., AND STOLF{, J. Primitives for manipulation of general subdivisions and the computation of Voronoi diagrams. ACM Trans. Graph. 4, 2 (April 1985), 74-123. Google Scholar
- 16 KNUTH, D.E. The Art of Computer Programming. Vol. 2, Seminumerical Algorithms. Addison- Wesley, Reading, Mass., 19~39. Google Scholar
- 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.Google Scholar
- 18 PREPARATA, F. P., AND HONG, S.J. Convex hulls of finite sets of points in two and three dimensions. Commun. ACM 20, 2 (Feb. 1977), 87-93. Google Scholar
- 19 PREPARATA, F. P., AND SHAMOS, M.I. Computational Geometry--An Introduction. Springer- Veriag, New York, 1985. Google Scholar
- 20 SEIDEL, R. A convex hull algorithm optimal for point sets in even dimensions. Tech. Rep. 81-14, Dept. of Computer Science, Univ. of British Columbia, Vancouver, British Columbia, 1981. Google Scholar
- 21 SEIDEL, R. On the size of closest-point Voronoi diagrams. Tech. Rep. F94, Institute fur Informationsverarbeitung, Technische Universitat Graz, Austria, 1982.Google Scholar
- 22 SEIDEL, R. Constructing higher-dimensional convex hulls in logarithmic cost per face. In Proceedings of ,~o 7~,~ a ... l 4t,~ q ... ; ... Theory ,~ r~ ... t;,o {n,~,b,~l,~,, ~A ~,,, 28-30), 1986, pp. 484-507. Google Scholar
- 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.Google Scholar
- 24 YAP, C.K. A geometric consistency theorem for a symbolic perturbation scheme. In Proceedings of the 4th Annual ACM Symposium on Computational Geometry (Urbana, Ill., June 6-8, 1988), pp. 134-142. Google Scholar
Index Terms
- Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms
Recommendations
Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms
SCG '88: Proceedings of the fourth annual symposium on Computational geometryThis 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 ...
Partial geometric difference sets and partial geometric difference families
AbstractThe concept of a partial geometric difference set (or 1 1 2-difference set) was introduced by Olmez in 2014. Recently, Nowak, Olmez and Song introduced the notion of a partial geometric difference family, which generalizes both the ...
Effects of success v failure cases on learner-learner interaction
Studies have found that students struggle to challenge their peers and engage in co-construction of knowledge when in asynchronous problem-based learning (PBL) contexts. In other settings, case libraries have been shown to support problem solving ...
Reviews
C. A. Neff
Anyone who has done even a moderate amount of computer programming has probably discovered that the proper handling of special cases can often turn the implementation of a conceptually simple algorithm into a real nightmare. The algorithms of computational geometry tend to be particularly fraught with special cases, most of which are relatively complex. This paper presents a systematic and robust method of handling the special cases occurring in a variety of these algorithms. The method discussed is very specific and at first seems quite narrow in scope. It is simply a way to consistently assign a sign, positive or negative, to a matrix determinant even when the determinant is actually zero (in effect, a careful way of breaking ties). Through a good set of examples in Section 5, the authors demonstrate that many of the logical branching decisions in computational geometry algorithms can be phrased in terms of the sign of a matrix determinant in such a way that special cases correspond to this determinant being exactly zero. Thus, by using the modified determinant sign computation whenever a determinant is called for, a programmer can legitimately assume that special cases never occur. From a mathematician's point of view, the paper is rather long; most of the details could probably be phrased much more succinctly in terms of the standard notation of linear and multilinear algebra. A programmer, on the other hand, may find the details related to proving the method's robustness somewhat distracting. The paper does take a good step in the direction of organizing geometric computations into a consistent framework, however; for a programmer, it is a refreshing change from the majority of computational geometry papers, which describe algorithms at such a high level that their implementation is essentially ignored. The set of references is good and thorough, but not crucial to understanding the paper.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments