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

DOI10.1145/77635.77639zbMath0732.68099arXivmath/9410209OpenAlexW2008581147MaRDI QIDQ3358264

Publication date: 1990

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

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

zbMATH Keywords

robustness reliability perturbation determinants geometric algorithms geometric software degenerate data programming 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)

Related Items

Robustness and Randomness, Kinetic Geodesic Voronoi Diagrams in a Simple Polygon, Continuous Histograms for Anisotropy of 2D Symmetric Piece-Wise Linear Tensor Fields, The centroid of points with approximate weights, Geometric hitting set for line-constrained disks, Exact and heuristic solutions for the prize‐collecting geometric enclosure problem, Delaunay and regular triangulations as lexicographic optimal chains, Stable Approximation Algorithms for the Dynamic Broadcast Range-Assignment Problem, Hierarchies and Ranks for Persistence Pairs, Pathological and Test Cases for Reeb Analysis, OVERLAYING SURFACE MESHES, PART I: ALGORITHMS, Algorithms for the line-constrained disk coverage and related problems, VRONI: An engineering approach to the reliable and efficient computation of Voronoi diagrams of points and line segments, Discrete Stratified Morse Theory: Algorithms and A User's Guide, Triangulating the surface of a molecule, Constrained routing between non-visible vertices, The weighted-volume derivative of a space-filling diagram, Unnamed Item, TetGen, a Delaunay-Based Quality Tetrahedral Mesh Generator, Topology-Oriented Incremental Algorithm for the Robust Construction of the Voronoi Diagrams of Disks, The Safari interface for visualizing time-dependent volume data using iso-surfaces and contour spectra, Solving the minimum convex partition of point sets with integer programming, A parallel algorithm for computing Voronoi diagram of a set of circles using touching disc and topology matching, Optimality of the Delaunay triangulation in \(\mathbb{R}^ d\), The complexity of the node capacitated in-tree packing problem, \(k\)-violation linear programming, Edge insertion for optimal triangulations, Finding a largest-area triangle in a terrain in near-linear time, Partial optimal transport for a constant-volume Lagrangian mesh with free boundaries, Computing colourful simplicial depth and Median in \(\mathbb{R}_2\), Semi-dynamic Connectivity in the Plane, The union of balls and its dual shape, On finding a widest empty 1-corner corridor, Approximating finite weighted point sets by hyperplanes, Robust Detection of Singularities in Vector Fields, A complete and efficient algorithm for the intersection of a general and a convex polyhedron, TOPOLOGICAL PEELING AND APPLICATIONS, Infimaximal Frames: A Technique for Making Lines Look Like Segments, On geometric optimization with few violated constraints, On topological changes in the Delaunay triangulation of moving points, Incremental topological flipping works for regular triangulations, Meshing skin surfaces with certified topology, Perturbations for Delaunay and weighted Delaunay 3D triangulations, Repairing unstructured triangular mesh intersections, Removing degeneracy may require unbounded dimension increase, Separating bichromatic point sets by L-shapes, A kinetic triangulation scheme for moving points in the plane, On shortest disjoint paths in planar graphs, Ham-sandwich cuts for abstract order types, On the power of the semi-separated pair decomposition, Gerris: A tree-based adaptive solver for the incompressible Euler equations in complex geometries., Computing multiparameter persistent homology through a discrete Morse-based approach, Parallel computation of alpha complexes for biomolecules, From crossing-free graphs on wheel sets to embracing simplices and polytopes with few vertices, Applied computational geometry: Towards robust solutions of basic problems, FARAWAY POINT: A SENTINEL POINT FOR DELAUNAY COMPUTATION, Morse connection graphs for piecewise constant vector fields on surfaces, Robust computation of Morse-Smale complexes of bilinear functions, The upper envelope of piecewise linear functions: Algorithms and applications, A robust and efficient hybrid cut-cell/ghost-cell method with adaptive mesh refinement for moving boundaries on irregular domains, A general approach to the analysis of controlled perturbation algorithms, Kinetic collision detection between two simple polygons., Čech-Delaunay gradient flow and homology inference for self-maps, Cutting hyperplane arrangements, Triangulating a simple polygon in linear time, A simple method for resolving degeneracies in Delaunay triangulations, Exact Fast Parallel Intersection of Large 3-D Triangular Meshes, A role of lower semicontinuous functions in the combinatorial complexity of geometric problems, There are simple and robust refinements (almost) as good as Delaunay, Randomized optimal algorithm for slope selection, Approximating polyhedral objects with deformable smooth surfaces, Polynomial-sized topological approximations using the permutahedron, Polyhedral perturbations that preserve topological form, Implementation of a randomized algorithm for Delaunay and regular triangulations in three dimensions, Discrete Lagrangian algorithm for finding geodesics on triangular meshes, Improved approximate Rips filtrations with shifted integer lattices and cubical complexes, Finding the largest area axis-parallel rectangle in a polygon, A dynamic sampling approach towards computing Voronoi diagram of a set of circles, Delaunay triangulations in three dimensions with finite precision arithmetic, 3D boundary recovery by constrained Delaunay tetrahedralization, SINK INSERTION FOR MESH IMPROVEMENT, Visibility maps of segments and triangles in 3D, PAINT: Pareto front interpolation for nonlinear multiobjective optimization, General-dimensional constrained Delaunay and constrained regular triangulations. I: Combinatorial properties, Intersection of unit-balls and diameter of a point set in \(\mathbb R^3\)., Cutting hyperplanes for divide-and-conquer, Preferred directions for resolving the non-uniqueness of Delaunay triangulations, Adaptive skin meshes coarsening for biomolecular simulation, Smooth kinetic maintenance of clusters, Unnamed Item, A CASE STUDY IN ALGORITHM ENGINEERING FOR GEOMETRIC COMPUTING, \texttt{ColDICE}: A parallel Vlasov-Poisson solver using moving adaptive simplicial tessellation, On Kinetic Delaunay Triangulations, A linear-time algorithm for the geodesic center of a simple polygon, Multiparametric linear programming with applications to control, Flexible isosurfaces: Simplifying and displaying scalar topology using the contour tree, A genus oblivious approach to cross parameterization, Unnamed Item, Intelligent Solutions for Curve Reconstruction Problem, Robust Point-Location in Generalized Voronoi Diagrams, Coupled hard-soft tissue simulation with contact and constraints applied to jaw-tongue-hyoid dynamics, Low complexity algorithms for optimal consumer push-pull partial covering in the plane, A perturbation scheme for spherical arrangements with application to molecular modeling, Crushing Disks Efficiently, A practical approximation algorithm for the LMS line estimator, Optimal output-sensitive convex hull algorithms in two and three dimensions, Output-sensitive results on convex hulls, extreme points, and related problems, Sign determination in residue number systems, Applications of random sampling in computational geometry. II, On the definition and the construction of pockets in macromolecules, Delaunay triangulation of imprecise points in linear time after preprocessing, Unnamed Item, Order-k Voronoi diagrams of sites with additive weights in the plane, Algorithms for bichromatic line-segment problems and polyhedral terrains, \texttt{PAINT-SICon}: constructing consistent parametric representations of Pareto sets in nonconvex multiobjective optimization, An Improved Ray Shooting Method for Constructive Solid Geometry Models Via Tree Contraction, A Complete Implementation for Computing General Dimensional Convex Hulls, A Robust Implementation for Three-Dimensional Delaunay Triangulations, An O\((n\log n)\) algorithm for the zoo-keeper's problem, Computing contour trees in all dimensions