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

1994/10/11 by Herbert Edelsbrunner, Edelsbrunner, Herbert, Ernst P. Mücke +1 · 11 citations
Computer Science · Engineering · #68Q #Advanced Numerical Analysis Techniques #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #FOS: Mathematics #Manufacturing Process and Optimization

paper · pdf · doi:10.48550/arxiv.math/9410209

openalex publication_date 1994/10/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This paper describes a general-purpose programming technique, called the\nSimulation of Simplicity, which can be used to cope with degenerate input data\nfor geometric algorithms. It relieves the programmer from the task to provide a\nconsistent treatment for every single special case that can occur. The programs\nthat use the technique tend to be considerably smaller and more robust than\nthose that do not use it. We believe that this technique will become a standard\ntool in writing geometric software.\n

Cited by

• Continuous Edit Distance, Geodesics and Barycenters of Time-varying Persistence Diagrams
• Largest-Area Convex Quadrilateral in a 1.5D Terrain
• Star-Based Separators for Intersection Graphs of c-Colored Pseudo-Segments
• Region-Aware Wasserstein Distances of Persistence Diagrams and Merge Trees
• Time-varying Vector Field Compression with Preserved Critical Point Trajectories
• Fast and Accurate Intersections on a Sphere
• Robust Geometric Predicates for Bivariate Computational Topology
• Topology Aware Neural Interpolation of Scalar Fields
• Topology-Aware Volume Fusion for Spectral Computed Tomography via Histograms and Extremum Graph
• Extremely Scalable Distributed Computation of Contour Trees via Pre-Simplification
• An Optimal Algorithm for Shortest Paths in Unweighted Disk Graphs

Related

• Implementing Simulation of Simplicity for geometric degeneracies
• Optimized Automatic Code Generation for Geometric Algebra Based Algorithms with Ray Tracing Application
• A Generic Lazy Evaluation Scheme for Exact Geometric Computations
• Introducing Geometric Algebra to Geometric Computing Software Developers: A Computational Thinking Approach
• Floating Point Geometric Algorithms for Topologically Correct Scientific Visualization