Two algorithms for constructing a Delaunay triangulation

DOI10.1007/BF00977785zbMath0441.68047OpenAlexW2002827932WikidataQ105583229 ScholiaQ105583229MaRDI QIDQ3883495

No author found.

Publication date: 1980

Published in: International Journal of Computer & Information Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf00977785

zbMATH Keywords

analysis of algorithmscomputational geometryDelaunay triangulationVoronoi tessellationdivide-and-conquer

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Polyhedra and polytopes; regular figures, division of spaces (51M20) Combinatorial aspects of tessellation and tiling problems (05B45)

Related Items

An extension to \textsc{Voro++} for multithreaded computation of Voronoi cells, Elliptical Slice Sampling for Probabilistic Verification of Stochastic Systems with Signal Temporal Logic Specifications, Convergence analysis of distributed population dynamics based on second-order Delaunay triangulation, Multiscale analysis of a 3D fibrous collagen tissue, Large deviation principle for geometric and topological functionals and associated point processes, Phase-field fracture analysis for implicit geometric model via adaptive extended isogeometric analysis, Generalized Delaunay triangulation for planar graphs, An O(N log N) minimal spanning tree algorithm for N points in the plane, Computing relative neighbourhood graphs in the plane, OPTIMAL DELAUNAY POINT INSERTION, Three-particle correlations in liquid and amorphous aluminium, DIMENSION-INDEPENDENT BSP (2): BOUNDARY-TO-INTERIOR MAPPING, A linear-time construction of the relative neighborhood graph from the Delaunay triangulation, Identifying parent locations in the Neyman-Scott process using Delaunay triangulation, A note on equity across groups in facility location, Covering part of a planar network, The planar multifacility collection depots location problem, The quintile share ratio in location analysis, Analysis of structure and strain at the meso-scale in 2D granular materials, A faster divide-and-conquer algorithm for constructing Delaunay triangulations, A linear-time construction of the relative neighborhood graph within a histogram, Location of a distribution center for a perishable product, A sweepline algorithm for Voronoi diagrams, A nonconvex, piecewise linear optimization problem, Direct zigzag search for discrete multi-objective optimization, Computational Color Imaging, A simple unstructured tetrahedral mesh generation algorithm for complex geometries, An efficient three-dimensional adaptive quasicontinuum method using variable-node elements, On a proposed divide-and-conquer minimal spanning tree algorithm, Constrained Delaunay triangulations, Evolutionary computation solutions to the circle packing problem, Creating rectangular bathymetry grids for environmental numerical modelling of gravel-bed rivers, Solving the planar \(p\)-Median problem by variable neighborhood and concentric searches, The meshfree finite volume method with application to multi-phase porous media models, An interface-fitted mesh generator and virtual element methods for elliptic interface problems, A physics-informed neural network technique based on a modified loss function for computational 2D and 3D solid mechanics, A scalable nonlinear fluid-structure interaction solver based on a Schwarz preconditioner with isogeometric unstructured coarse spaces in 3D, Gradient and uncertainty enhanced sequential sampling for global fit, The Weber Location Problem: The Threshold Objective, Unnamed Item, Bayesian clustering of spatial functional data with application to a human mobility study during COVID-19, Gradual cover competitive facility location, A faster circle-sweep Delaunay triangulation algorithm, Topology optimization of compliant structures and mechanisms using constructive solid geometry for 2-d and 3-d applications, Remarks on the computation of the horizon of a digital terrain, A straightforward iterative algorithm for the planar Voronoi diagram, Shortest paths and convex hulls in 2D complexes with non-positive curvature, A divide-and-conquer algorithm for constructing relative neighborhood graph, Interior boundary-aligned unstructured grid generation and cell-centered versus vertex-centered CVD-MPFA performance, Fitting concentric circles to measurements, Graph theoretical clustering based on limited neighbourhood sets, On the statistics of vision: The Julesz conjecture, Integrating the supervised information into unsupervised learning, Application of NEM in seepage analysis with a free surface, Segment-based vs. element-based integration for mortar methods in computational contact mechanics, Ambiguous phase assignment of discretized 3D geometries in topology optimization, Why is the 3D Delaunay triangulation difficult to construct?, A data modeling abstraction for describing triangular mesh algorithms, The obnoxious facilities planar \(p\)-median problem, PORA: a Physarum-inspired obstacle-avoiding routing algorithm for integrated circuit design, The \(\gamma\)-neighborhood graph, New local searches for solving the multi-source Weber problem, The wisdom of voters: evaluating the Weber objective in the plane at the Condorcet solution, Maximizing the minimum cover probability by emergency facilities, Recursive learning for sparse Markov models, Reprint of: Delaunay refinement algorithms for triangular mesh generation, Fully dynamic Delaunay triangulation in logarithmic expected per operation, A scoring mechanism for the rank aggregation of network robustness, Two simple algorithms for constructing a two-dimensional constrained Delaunay triangulation, On the randomized construction of the Delaunay tree, An adaptive mesh algorithm for evolving surfaces: simulations of drop breakup and coalescence, Relaxation methods for constrained matrix factorization problems: solving the phase mapping problem in materials discovery, Generalized coverage: new developments in covering location models, Rapid prototyping through scanned point data, The maximum opposite angulation for mesh construction, Three-dimensional unstructured gridding for complex wells and geological features in subsurface reservoirs, with CVD-MPFA discretization performance, Second generation wavelets based GIS terrain data compression using Delaunay triangulation, The natural element method in solid mechanics, A distributed algorithm to maintain a proximity communication network among mobile agents using the Delaunay triangulation, The shape optimization of the arterial graft design by level set methods, Solving scheduling and location problems in the plane simultaneously, Stability Analysis and Parameter Classification of a Reaction-Diffusion Model on an Annulus, Bayesian Inference for a Random Tessellation Process, Interpolation of sparse high-dimensional data, An O(n log n) plane-sweep algorithm for \(L_ 1\) and \(L_{\infty}\) Delaunay triangulations, Two design principles of geometric algorithms in finite-precision arithmetic, Minimal roughness property of the Delaunay triangulation, An adaptive binary-tree element subdivision method for evaluation of volume integrals with continuous or discontinuous kernels, On constructing the relative neighborhood graphs in Euclidean k- dimensional spaces, Optimal speeding up of parallel algorithms based upon the divide-and- conquer strategy, There are planar graphs almost as good as the complete graph, Big segment small segment global optimization algorithm on networks, Learning constitutive relations from indirect observations using deep neural networks, A probabilistic result on multi-dimensional Delaunay triangulations, and its application to the 2D case, Breakthrough `workarounds' in unstructured mesh generation, A constrained clustering approach to bounded-error identification of switched and piecewise affine systems, Delaunay triangulation and the convex hull of n points in expected linear time, On the average length of Delaunay triangulations, Complementary error bounds for foolproof finite element mesh generation, On the complexity of two circle connecting problems, Exact approaches for the minimum subgraph diameter problem, Delaunay refinement algorithms for triangular mesh generation, Modeling of Acoustic Signal Energies with a Generalized Frank Copula. A Linguistic Conjecture is Reviewed, Robust optimization of attenuation bands of three-dimensional periodic frame structures, Fast segment insertion and incremental construction of constrained Delaunay triangulations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Triangulating a simple polygon
• A triangulation algorithm for arbitrary planar domains
• On the homogeneous planar Poisson point process
• Reconstructing Patterns from Sample Data
• Two Dimensional Interpolation from Random Data
• Convex hulls of finite sets of points in two and three dimensions
• Piecewise Quadratic Approximations on Triangles
• Computing Dirichlet Tessellations in the Plane
• Packing of congruent spheres in a strip
• Triangulation of planar regions with applications
• Decomposition of Polygons into Convex Sets
• Random Subdivisions of Space into Crystals