Delaunay triangulation and the convex hull of n points in expected linear time
From MaRDI portal
Publication:799379
DOI10.1007/BF01937482zbMath0548.68068MaRDI QIDQ799379
Publication date: 1984
Published in: BIT (Search for Journal in Brave)
Euclidean planeconvex hulllinear time algorithmDelaunay triangulationVoronoi polygonsRadix-sort algorithm
Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Combinatorial aspects of partitions of integers (05A17) Polyhedra and polytopes; regular figures, division of spaces (51M20) Convex sets in (2) dimensions (including convex curves) (52A10) Discrete mathematics in relation to computer science (68R99)
Related Items
Computing relative neighbourhood graphs in the plane, A faster divide-and-conquer algorithm for constructing Delaunay triangulations, A linear expected-time algorithm for computing planar relative neighbourhood graphs, DELAUNAY PARTITIONING IN THREE DIMENSIONS AND SEMICONDUCTOR MODELS, A faster circle-sweep Delaunay triangulation algorithm, A straightforward iterative algorithm for the planar Voronoi diagram, An efficient and numerically correct algorithm for the 2D convex hull problem, A comparison of sequential Delaunay triangulation algorithms., An O(n log n) plane-sweep algorithm for \(L_ 1\) and \(L_{\infty}\) Delaunay triangulations, Automatic mesh generation for finite element analysis, Fast Delaunay triangulation in three dimensions, A probabilistic result on multi-dimensional Delaunay triangulations, and its application to the 2D case, Higher-dimensional Voronoi diagrams in linear expected time
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A constant-time parallel algorithm for computing convex hulls
- An efficient algorithm for determining the convex hull of a finite planar set
- Two algorithms for constructing a Delaunay triangulation
- Two-Dimensional Voronoi Diagrams in the L p -Metric
- A New Convex Hull Algorithm for Planar Sets
- Computing Dirichlet Tessellations in the Plane
