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