Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms
From MaRDI portal
Publication:3358264
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
reliabilityrobustnessperturbationdeterminantsgeometric algorithmsgeometric softwaredegenerate dataprogramming tool
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)
- 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
- Separating bichromatic point sets by L-shapes
- A role of lower semicontinuous functions in the combinatorial complexity of geometric problems
- The centroid of points with approximate weights
- On kinetic Delaunay triangulations: a near-quadratic bound for unit speed motions
- On geometric optimization with few violated constraints
- On shortest disjoint paths in planar graphs
- Semi-dynamic connectivity in the plane
- VRONI: An engineering approach to the reliable and efficient computation of Voronoi diagrams of points and line segments
- Smooth kinetic maintenance of clusters
- Computing contour trees in all dimensions
- A general approach to the analysis of controlled perturbation algorithms
- The upper envelope of piecewise linear functions: Algorithms and applications
- \texttt{ColDICE}: A parallel Vlasov-Poisson solver using moving adaptive simplicial tessellation
- Flexible isosurfaces: Simplifying and displaying scalar topology using the contour tree
- A Robust Implementation for Three-Dimensional Delaunay Triangulations
- Applied computational geometry: Towards robust solutions of basic problems
- Gerris: A tree-based adaptive solver for the incompressible Euler equations in complex geometries.
- Kinetic collision detection between two simple polygons.
- Multiparametric linear programming with applications to control
- Intersection of unit-balls and diameter of a point set in \(\mathbb R^3\).
- Preferred directions for resolving the non-uniqueness of Delaunay triangulations
- TetGen, a Delaunay-based quality tetrahedral mesh generator
- A Complete Implementation for Computing General Dimensional Convex Hulls
- Adaptive skin meshes coarsening for biomolecular simulation
- Implementation of a randomized algorithm for Delaunay and regular triangulations in three dimensions
- 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
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)
