Construction of three-dimensional Delaunay triangulations using local transformations
From MaRDI portal
For a set of points in \(R^ 3\) the problem of Delaunay triangulation is to find a set of nonoverlapping tetrahedra that fill the convex hull of the set so that no point is in the circumscribed sphere of any tetrahedron of which it is not a vertex. The author gives the pseudocode description of two programs that solve the problem by local decisions involving five points at a time and proves that the worst case time complexity is \(O(n^ 2)\) and the expected complexity for random points is O(n(log n)\({}^ 2)\).
Recommendations
- Three-Dimensional Triangulations from Local Transformations
- Implementation of a randomized algorithm for Delaunay and regular triangulations in three dimensions
- OPTIMAL DELAUNAY POINT INSERTION
- Fast Delaunay triangulation in three dimensions
- Construction of K-Dimensional Delaunay Triangulations Using Local Transformations
Cites work
- A fast algorithm for constructing Delaunay triangulations in the plane
- An apporach to automatic three-dimensional finite element mesh generation
- Delaunay Triangular Meshes in Convex Polygons
- scientific article; zbMATH DE number 3919830 (Why is no real title available?)
- scientific article; zbMATH DE number 4032498 (Why is no real title available?)
- scientific article; zbMATH DE number 3473265 (Why is no real title available?)
- scientific article; zbMATH DE number 3633698 (Why is no real title available?)
- On the Average Number of Maxima in a Set of Vectors and Applications
- Properties of n-dimensional triangulations
- Tetrahedrizing point sets in three dimensions
- Three-Dimensional Triangulations from Local Transformations
Cited in
(50)- Approximating constrained tetrahedrizations
- Flow simulation and high performance computing
- Optimal tetrahedral mesh generation for three-dimensional point set
- 3D simulation of fluid-particle interactions with the number of particles reaching 100
- The hybrid quintic Bézier tetrahedron
- Regular triangulations of dynamic sets of points
- Structural tolerance and Delaunay triangulation
- Interior boundary-aligned unstructured grid generation and cell-centered versus vertex-centered CVD-MPFA performance
- Pointwise rates of convergence for the Oliker-Prussner method for the Monge-Ampère equation
- Construction of the Delaunay superlarge triangulation
- A 3D flow-aligning algorithm for convection-diffusion problems
- Projections of polytopes and the generalized Baues conjecture
- Triangulating point sets in space
- On local transformation of polygons with visibility properties.
- Incremental topological flipping works for regular triangulations
- Piecewise linear approximation by the method of worst segment division
- Breakthrough `workarounds' in unstructured mesh generation
- The singularity set of optimal transportation maps
- Secondary polytope and secondary power diagram
- Fast Delaunay triangulation in three dimensions
- Automatic generation of transitional meshes.
- 2D and 3D finite element meshing and remeshing. A bibliography (1990-2001)
- scientific article; zbMATH DE number 1728310 (Why is no real title available?)
- A Duality Transform for Constructing Small Grid Embeddings of 3D Polytopes
- Complexity of Delaunay triangulation for points on lower-dimensional polyhedra
- A quasi-static dual particle method for solids based on dual particle dynamics
- The particle finite element method (PFEM) in thermo-mechanical problems
- Small polyhedron reconnection for mesh improvement and its implementation based on advancing front technique
- A probabilistic approach to reducing algebraic complexity of Delaunay triangulations
- Flip Algorithm for Segment Triangulations
- A fast algorithm for constructing Delaunay triangulations in the plane
- Construction of K-Dimensional Delaunay Triangulations Using Local Transformations
- scientific article; zbMATH DE number 1036609 (Why is no real title available?)
- Generation of non-isotropic unstructured grids via directional enrichment
- Three-Dimensional Triangulations from Local Transformations
- ENUMERATING TRIANGULATIONS IN GENERAL DIMENSIONS
- SIMULTANEOUS EDGE FLIPPING IN TRIANGULATIONS
- scientific article; zbMATH DE number 2119654 (Why is no real title available?)
- OUTPUT SENSITIVE CONSTRUCTION OF THE DELAUNAY TRIANGULATION OF POINTS LYING IN TWO PLANES
- The Singularity Set of Optimal Transportation Maps
- Secondary power diagram, dual of secondary polytope
- Guaranteed-quality parallel Delaunay refinement for restricted polyhedral domains
- Geometric triangulations and discrete Laplacians on manifolds: an update
- The legacy of automatic mesh generation from solid modeling
- Implementation of a randomized algorithm for Delaunay and regular triangulations in three dimensions
- Flips in two-dimensional hypertriangulations
- An approach for Delaunay tetrahedralization of bodies with curved boundaries
- Small polyhedron reconnection: a new way to eliminate poorly-shaped tetrahedra
- Delaunay triangulation and the convex hull of n points in expected linear time
- Constrained paths in the flip-graph of regular triangulations
This page was built for publication: Construction of three-dimensional Delaunay triangulations using local transformations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q807005)
