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)- 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
- A CASE STUDY IN ALGORITHM ENGINEERING FOR GEOMETRIC COMPUTING
- Topology-oriented incremental algorithm for the robust construction of the Voronoi diagrams of disks
- Kernelization of the subset general position problem in geometry
- On the definition and the construction of pockets in macromolecules
- scientific article; zbMATH DE number 7236405 (Why is no real title available?)
- A kinetic triangulation scheme for moving points in the plane
- Separating bichromatic point sets by L-shapes
- From image to video approximation by adaptive splines over tetrahedralizations
- A role of lower semicontinuous functions in the combinatorial complexity of geometric problems
- 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
- On shortest disjoint paths in planar graphs
- On geometric optimization with few violated constraints
- On kinetic Delaunay triangulations: a near-quadratic bound for unit speed motions
- The centroid of points with approximate weights
- Semi-dynamic connectivity in the plane
- Smooth kinetic maintenance of clusters
- A general approach to the analysis of controlled perturbation algorithms
- VRONI: An engineering approach to the reliable and efficient computation of Voronoi diagrams of points and line segments
- The upper envelope of piecewise linear functions: Algorithms and applications
- \texttt{ColDICE}: A parallel Vlasov-Poisson solver using moving adaptive simplicial tessellation
- Computing contour trees in all dimensions
- The extended persistent homology transform of manifolds with boundary
- Flexible isosurfaces: Simplifying and displaying scalar topology using the contour tree
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)
