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

DOI10.1145/77635.77639zbMATH Open0732.68099arXivmath/9410209OpenAlexW2008581147MaRDI QIDQ3358264FDOQ3358264

Authors: E. P. Mücke, Herbert Edelsbrunner 

Publication date: 1990

Published in: ACM Transactions on Graphics (Search for Journal in Brave)

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 that do not use it. We believe that this technique will become a standard tool in writing geometric software.

Full work available at URL: https://arxiv.org/abs/math/9410209

Recommendations

• scientific article; zbMATH DE number 1003230
• Simplicial algorithms on the simplotope
• scientific article; zbMATH DE number 3852808
• General similitude solutions and low-complexity geometric models
• scientific article; zbMATH DE number 4051370
• scientific article; zbMATH DE number 4078610
• A New Triangulation for Simplicial Algorithms
• A simple method for resolving degeneracies in Delaunay triangulations

zbMATH Keywords

reliabilityrobustnessperturbationdeterminantsgeometric algorithmsgeometric softwaredegenerate dataprogramming tool

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cited In (only showing first 100 items - show all)

• One machine, one minute, three billion tetrahedra
• Discrete Lagrangian algorithm for finding geodesics on triangular meshes
• Geometric hitting set for line-constrained disks
• Robustness issues in geometric algorithms
• Hybrid meshing using constrained Delaunay triangulation for viscous flow simulations
• Intelligent Solutions for Curve Reconstruction Problem
• Morse connection graphs for piecewise constant vector fields on surfaces
• Robust Point-Location in Generalized Voronoi Diagrams
• Computing multiparameter persistent homology through a discrete Morse-based approach
• There are simple and robust refinements (almost) as good as Delaunay
• Exact and heuristic solutions for the prize‐collecting geometric enclosure problem
• Kinetic Geodesic Voronoi Diagrams in a Simple Polygon
• Improved approximate Rips filtrations with shifted integer lattices and cubical complexes
• A dynamic sampling approach towards computing Voronoi diagram of a set of circles
• Čech-Delaunay gradient flow and homology inference for self-maps
• Partial optimal transport for a constant-volume Lagrangian mesh with free boundaries
• Computing colourful simplicial depth and Median in \(\mathbb{R}_2\)
• On the line-separable unit-disk coverage and related problems
• Remark on Algorithm 1012: computing projections with large datasets
• \texttt{PAINT-SICon}: constructing consistent parametric representations of Pareto sets in nonconvex multiobjective optimization
• Delaunay and regular triangulations as lexicographic optimal chains
• Pathological and Test Cases for Reeb Analysis
• Continuous Histograms for Anisotropy of 2D Symmetric Piece-Wise Linear Tensor Fields
• A simple method for resolving degeneracies in Delaunay triangulations
• 3D boundary recovery by constrained Delaunay tetrahedralization
• An Improved Ray Shooting Method for Constructive Solid Geometry Models Via Tree Contraction
• SINK INSERTION FOR MESH IMPROVEMENT
• Decomposing the complement of the union of cubes and boxes in three dimensions
• FARAWAY POINT: A SENTINEL POINT FOR DELAUNAY COMPUTATION
• A CASE STUDY IN ALGORITHM ENGINEERING FOR GEOMETRIC COMPUTING
• Robust computation of Morse-Smale complexes of bilinear functions
• Topology-oriented incremental algorithm for the robust construction of the Voronoi diagrams of disks
• Kernelization of the subset general position problem in geometry
• Title not available (Why is that?)
• From image to video approximation by adaptive splines over tetrahedralizations
• The complexity of the node capacitated in-tree packing problem
• Visibility maps of segments and triangles in 3D
• Stable Approximation Algorithms for the Dynamic Broadcast Range-Assignment Problem
• The extended persistent homology transform of manifolds with boundary
• Discrete Stratified Morse Theory: Algorithms and A User's Guide
• Coupled hard-soft tissue simulation with contact and constraints applied to jaw-tongue-hyoid dynamics
• Approximating polyhedral objects with deformable smooth surfaces
• Hierarchies and Ranks for Persistence Pairs
• Robustness and Randomness
• Delaunay triangulations in three dimensions with finite precision arithmetic
• Title not available (Why is that?)
• Approximating finite weighted point sets by hyperplanes
• A parallel algorithm for computing Voronoi diagram of a set of circles using touching disc and topology matching
• The weighted-volume derivative of a space-filling diagram
• Removing degeneracy may require unbounded dimension increase
• Crushing disks efficiently
• From crossing-free graphs on wheel sets to embracing simplices and polytopes with few vertices
• Robust detection of singularities in vector fields
• Algorithms for bichromatic line-segment problems and polyhedral terrains
• Solving the minimum convex partition of point sets with integer programming
• Algorithms for the line-constrained disk coverage and related problems
• Repairing unstructured triangular mesh intersections
• Finding a largest-area triangle in a terrain in near-linear time
• Cutting hyperplane arrangements
• Delaunay triangulation of imprecise points in linear time after preprocessing
• TOPOLOGICAL PEELING AND APPLICATIONS
• A complete and efficient algorithm for the intersection of a general and a convex polyhedron
• Finding the largest area axis-parallel rectangle in a polygon
• General-dimensional constrained Delaunay and constrained regular triangulations. I: Combinatorial properties
• On finding a widest empty 1-corner corridor
• Order-k Voronoi diagrams of sites with additive weights in the plane
• Triangulating the surface of a molecule
• Polynomial-sized topological approximations using the permutahedron
• Title not available (Why is that?)
• A perturbation scheme for spherical arrangements with application to molecular modeling
• On the power of the semi-separated pair decomposition
• Exact Fast Parallel Intersection of Large 3-D Triangular Meshes
• Meshing skin surfaces with certified topology
• A practical approximation algorithm for the LMS line estimator
• Polyhedral perturbations that preserve topological form
• Cutting hyperplanes for divide-and-conquer
• A robust and efficient hybrid cut-cell/ghost-cell method with adaptive mesh refinement for moving boundaries on irregular domains
• A linear-time algorithm for the geodesic center of a simple polygon
• OVERLAYING SURFACE MESHES, PART I: ALGORITHMS
• Optimality of the Delaunay triangulation in \(\mathbb{R}^ d\)
• Applications of random sampling in computational geometry. II
• Optimal output-sensitive convex hull algorithms in two and three dimensions
• Triangulating a simple polygon in linear time
• An O\((n\log n)\) algorithm for the zoo-keeper's problem
• Sign determination in residue number systems
• Incremental topological flipping works for regular triangulations
• \(k\)-violation linear programming
• Edge insertion for optimal triangulations
• The Safari interface for visualizing time-dependent volume data using iso-surfaces and contour spectra
• A genus oblivious approach to cross parameterization
• Low complexity algorithms for optimal consumer push-pull partial covering in the plane
• Perturbations for Delaunay and weighted Delaunay 3D triangulations
• Infimaximal Frames: A Technique for Making Lines Look Like Segments
• Output-sensitive results on convex hulls, extreme points, and related problems
• The union of balls and its dual shape
• Randomized optimal algorithm for slope selection
• Parallel computation of alpha complexes for biomolecules
• PAINT: Pareto front interpolation for nonlinear multiobjective optimization
• On the definition and the construction of pockets in macromolecules
• A kinetic triangulation scheme for moving points in the plane

This page was built for publication: Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3358264)