Construction of <i>K</i>-Dimensional Delaunay Triangulations Using Local Transformations
SIAM Journal on Scientific ComputingPublished 1 November 1993
Barry Joe
Citations25
SJR quartileQ1
SJR score1.63
SNIP1.76
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
It is proved that local transformations can be used to construct a Delaunay triangulation of a set of nk-dimensional points for any $k \geq 2$ and algorithms using this approach are presented.
Abstract
In [SIAM J. Sci. Statist. Comput.,10 (1989), pp. 718–741] and [Comput. Aided Geom. Des., 8 (1991), pp. 123–142] the author presented algorithms that use local transformations to construct a Delaunay triangulation of a set of n three-dimensional points. This paper proves that local transformations can be used to construct a Delaunay triangulation of a set of nk-dimensional points for any $k \geq 2$, and presents algorithms using this approach. The empirical time complexities of these algorithms are discussed for sets of random points from the uniform distribution as well as worst-case time complexities. These time complexities are about the same or better than those of other algorithms for constructing k-dimensional Delaunay triangulations (when $k \geq 3$).
Keywords
Computer ScienceEnvironmental Science
Computational Geometry
3,606 Citations1985Franco P. Preparata, Michael Ian Shamos
This book clearly demonstrates that computational geometry in the plane is now a fairly well-understood branch of computer science and mathematics and points the way to the solution of the more challenging problems in dimensions higher than two.
International Journal of Parallel ProgrammingTwo algorithms for constructing a Delaunay triangulation
1,568 Citations1980D. T. Lee, Bruce J. Schachter
This paper provides a unified discussion of the Delaunay triangulation and two algorithms are presented for constructing the triangulations over a planar set ofN points.
Algorithms in Combinatorial Geometry
1,516 Citations1987Herbert Edelsbrunner
This book offers a modern approach to computational geo- metry, an area thatstudies the computational complexity of geometric problems with an important role in this study.
The Computer JournalComputing the n-dimensional Delaunay tessellation with application to Voronoi polytopes
1,459 Citations1981David F. Watson
AlgorithmicaA sweepline algorithm for Voronoi diagrams
1,119 Citations1987Steven Fortune
A geometric transformation is introduced that allows Voronoi diagrams to be computed using a sweepline technique and is used to obtain simple algorithms for computing the Vor onoi diagram of point sites, of line segment sites, and of weighted point sites.
Elsevier eBooksSoftware for C1 Surface Interpolation
733 Citations1977C. L. Lawson
This chapter discusses algorithm and underlying theory of software for C1 surface interpolation, an interpolation algorithm that is interfaced with algorithms for contour plotting or surface perspective plotting for data given on a rectangular grid.
Communications of the ACMConvex hulls of finite sets of points in two and three dimensions
706 Citations1977F. P. Preparata, S. J. Hong
The presented algorithms use the “divide and conquer” technique and recursively apply a merge procedure for two nonintersecting convex hulls to ensure optimal time complexity within a multiplicative constant.
International Journal for Numerical Methods in EngineeringAn apporach to automatic three‐dimensional finite element mesh generation
373 Citations1985James C. Caendish, David A. Field +1 more
The purpose of this paper is to describe an interactive solid mesh generation system capable of generating valid meshes of well-proportional tetrahedral finite elements for the decomposition of multiply connected solid structures.
Advances in Engineering Software (1978)A fast algorithm for constructing Delaunay triangulations in the plane
232 Citations1987Scott W. Sloan
An algorithm for computing Delaunay triangulations of arbitrary collections of points in the plane using FORTRAN 77 for the generation of finite element meshes and the construction of contour plots is described.
Computer Aided Geometric DesignConstruction of three-dimensional Delaunay triangulations using local transformations
231 Citations1991Barry Joe
It is proved that the conjecture that an algorithm which uses local transformations to construct a triangulation of a set of n three-dimensional points that is pseudo-locally-optimal with respect to the sphere criterion is true, and that the algorithm can be improved by removing unnecessary tests.
Computer Aided Geometric DesignProperties of n-dimensional triangulations
183 Citations1986C. L. Lawson
A number of mathematical results relevant to the problem of constructing a triangulation, i.e., a simplical tessellation of the convex hull of an arbitrary finite set of points in n-space are established.
SIAM Journal on Scientific and Statistical ComputingThree-Dimensional Triangulations from Local Transformations
181 Citations1989Barry Joe
A new algorithm is presented that uses a local transformation procedure to construct a triangulation of a set of n three-dimensional points that is pseudo-locally optimal with respect to the sphere criterion and it is conjectured that this algorithm always constructs a Delaunay triangulated.
International Journal for Numerical Methods in EngineeringA combined octree/delaunay method for fully automatic 3‐D mesh generation
150 Citations1990W. J. Schroeder, Mark S. Shephard
A method that combines both approaches to fully automatic mesh generation is presented, which provides the linear growth rate and divide-and-conquer approach of the octree method with the simplicity and optimal properties of the Delaunay triangulation.
International Journal for Numerical Methods in EngineeringDelaunay versus max‐min solid angle triangulations for three‐dimensional mesh generation
87 Citations1991Barry Joe
Experimental results are presented to show that max-min solid angle triangulations are better than Delaunay triangulated for finite element tetrahedral meshes, since the former type of triangulation contains tetrahedra of better shape than the latter type.
SIAM Journal on Scientific and Statistical ComputingDelaunay Triangular Meshes in Convex Polygons
58 Citations1986Barry Joe
An algorithm for producing a triangular mesh in a convex polygon is presented and the expected time complexity is shown to be linear in the number of triangles in the mesh.
Journal of Applied ProbabilityOn the convex hull of random points in a polytope
55 Citations1988Rex A. Dwyer
COMBINATORICAOn triangulations of the convex hull ofn points
27 Citations1985B. L. Rotschild, E. G. Straus
Those setsS for which all triangulations minimizem are characterized are used to characterize sets of points maximizing the volume of the smallest non-trivial simplex.