Delaunay triangulation and the convex hull of n points in expected linear time
type: Item
instance of: scholarly article
title: Delaunay triangulation and the convex hull of n points in expected linear time
zbMATH Open document ID: 0548.68068
DOI: 10.1007/BF01937482
author: A. Maus
published in: BIT
publication date: 1984-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68R99
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 52A10
Mathematics Subject Classification ID: 68P10
Mathematics Subject Classification ID: 05A17
Mathematics Subject Classification ID: 51M20
zbMATH DE Number: 3874637
zbMATH Keywords: Voronoi polygons
zbMATH Keywords: Delaunay triangulation
zbMATH Keywords: Radix-sort algorithm
zbMATH Keywords: linear time algorithm
zbMATH Keywords: convex hull
zbMATH Keywords: Euclidean plane
MaRDI profile type: Publication
cites work: Q4091421
cites work: A constant-time parallel algorithm for computing convex hulls
cites work: Q4760292
cites work: A New Convex Hull Algorithm for Planar Sets
cites work: An efficient algorithm for determining the convex hull of a finite planar set
cites work: Computing Dirichlet Tessellations in the Plane
cites work: Two-Dimensional Voronoi Diagrams in the L p -Metric
cites work: Two algorithms for constructing a Delaunay triangulation
cites work: Q3875133
description: scientific article; zbMATH DE number 3874637