An O(n log n) plane-sweep algorithm for L_ 1 and L_ Delaunay triangulations

DOI10.1007/BF01759042MaRDI QIDQ749241zbMATH OpenFDO

Authors Gary M. Shute, Linda L. Deneen, Clark D. Thomborson

Publication date 1991

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01759042

zbMATH Keywords

\(L_ 1\)-metric\(L_{\infty }\)- metriccomputational geometryDelaunay triangulationminimal spanning treeplane-sweep algorithmVoronoi diagram

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• A faster divide-and-conquer algorithm for constructing Delaunay triangulations
• Computing correct Delaunay triangulations
• A fast algorithm for constructing Delaunay triangulations in the plane
• Delaunay triangulation and the convex hull of n points in expected linear time
• A sweepline algorithm for Voronoi diagrams

Cites work

• An O ( n log n ) Algorithm for Rectilinear Minimal Spanning Trees
• An O(n log n) algorithm for suboptimal rectilinear Steiner trees
• Delaunay triangulation and the convex hull of n points in expected linear time
• Generalization of Voronoi Diagrams in the Plane
• scientific article; zbMATH DE number 3911704 (Why is no real title available?)
• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• Primitives for the manipulation of general subdivisions and the computation of Voronoi
• The greedy and Delaunay triangulations are not bad in the average case
• The Relative Neighborhood Graph, with an Application to Minimum Spanning Trees
• The relative neighbourhood graph of a finite planar set
• Two algorithms for constructing a Delaunay triangulation
• Two-Dimensional Voronoi Diagrams in the L _p -Metric
• Use of Steiner's problem in suboptimal routing in rectilinear metric
• Voronoui Diagrams in L₁ (L_\infty ) Metrics with 2-Dimensional Storage Applications

Cited in

(9)

• Computing correct Delaunay triangulations
• Efficient minimum spanning tree construction with Delaynay triangulation
• Persistent homology in \(\ell_\infty\) metric
• ``The big sweep: On the power of the wavefront approach to Voronoi diagrams
• A connectivity graph generation approach for Manhattan path calculation in detailed facility layout
• Delaunay properties of digital straight segments
• scientific article; zbMATH DE number 1786514 (Why is no real title available?)
• “The big sweep”: On the power of the wavefront approach to Voronoi diagrams
• Computational Science and Its Applications – ICCSA 2004

This page was built for publication: An O(n log n) plane-sweep algorithm for \(L_ 1\) and \(L_{\infty}\) Delaunay triangulations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q749241)