Delaunay triangulation and the convex hull of n points in expected linear time (Q799379): Difference between revisions

From MaRDI portal
Added link to MaRDI item.
ReferenceBot (talk | contribs)
Changed an Item
 
(One intermediate revision by one other user not shown)
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4091421 / rank
 
Normal rank
Property / cites work
 
Property / cites work: A constant-time parallel algorithm for computing convex hulls / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4760292 / rank
 
Normal rank
Property / cites work
 
Property / cites work: A New Convex Hull Algorithm for Planar Sets / rank
 
Normal rank
Property / cites work
 
Property / cites work: An efficient algorithm for determining the convex hull of a finite planar set / rank
 
Normal rank
Property / cites work
 
Property / cites work: Computing Dirichlet Tessellations in the Plane / rank
 
Normal rank
Property / cites work
 
Property / cites work: Two-Dimensional Voronoi Diagrams in the <i> L <sub>p</sub> </i> -Metric / rank
 
Normal rank
Property / cites work
 
Property / cites work: Two algorithms for constructing a Delaunay triangulation / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3875133 / rank
 
Normal rank

Latest revision as of 14:46, 14 June 2024

scientific article
Language Label Description Also known as
English
Delaunay triangulation and the convex hull of n points in expected linear time
scientific article

    Statements

    Delaunay triangulation and the convex hull of n points in expected linear time (English)
    0 references
    0 references
    0 references
    1984
    0 references
    An algorithm is presented which produces a Delaunay triangulation of n points in the Euclidean plane in expected linear time. The expected execution time is achieved when the data are (not too far from) uniformly distributed. A modification of the algorithm discussed in the appendix treats most of the non-uniform distributions. The basis of this algorithm is a geographical partitioning of the plane into boxes by the well-known Radix-sort algorithm. This partitioning is also used as a basis for a linear time algorithm for finding the convex hull of n points in the Euclidean plane.
    0 references
    Voronoi polygons
    0 references
    Delaunay triangulation
    0 references
    Radix-sort algorithm
    0 references
    linear time algorithm
    0 references
    convex hull
    0 references
    Euclidean plane
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references