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 plane; convex hull; linear time algorithm; Delaunay triangulation; Voronoi polygons; Radix-sort algorithm
68Q25: Analysis of algorithms and problem complexity
68P10: Searching and sorting
05A17: Combinatorial aspects of partitions of integers
51M20: Polyhedra and polytopes; regular figures, division of spaces
52A10: Convex sets in (2) dimensions (including convex curves)
68R99: Discrete mathematics in relation to computer science
Related Items
A faster circle-sweep Delaunay triangulation algorithm, An O(n log n) plane-sweep algorithm for \(L_ 1\) and \(L_{\infty}\) Delaunay triangulations, Automatic mesh generation for finite element analysis, Higher-dimensional Voronoi diagrams in linear expected time, A straightforward iterative algorithm for the planar Voronoi diagram, An efficient and numerically correct algorithm for the 2D convex hull problem, 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, A probabilistic result on multi-dimensional Delaunay triangulations, and its application to the 2D case, A comparison of sequential Delaunay triangulation algorithms., Fast Delaunay triangulation in three dimensions, DELAUNAY PARTITIONING IN THREE DIMENSIONS AND SEMICONDUCTOR MODELS
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
