An O(n log n) plane-sweep algorithm for \(L_ 1\) and \(L_{\infty}\) Delaunay triangulations
From MaRDI portal
Publication:749241
DOI10.1007/BF01759042zbMath0712.68102MaRDI QIDQ749241
Clark D. Thomborson, Linda L. Deneen, Gary M. Shute
Publication date: 1991
Published in: Algorithmica (Search for Journal in Brave)
Voronoi diagramcomputational geometryDelaunay triangulationminimal spanning tree\(L_ 1\)-metric\(L_{\infty }\)- metricplane-sweep algorithm
Related Items (5)
A connectivity graph generation approach for Manhattan path calculation in detailed facility layout ⋮ ``The big sweep: On the power of the wavefront approach to Voronoi diagrams ⋮ “The big sweep”: On the power of the wavefront approach to Voronoi diagrams ⋮ Persistent homology in \(\ell_\infty\) metric ⋮ Efficient minimum spanning tree construction with Delaynay triangulation
Cites Work
- Unnamed Item
- Unnamed Item
- Delaunay triangulation and the convex hull of n points in expected linear time
- The greedy and Delaunay triangulations are not bad in the average case
- The relative neighbourhood graph of a finite planar set
- The Relative Neighborhood Graph, with an Application to Minimum Spanning Trees
- Primitives for the manipulation of general subdivisions and the computation of Voronoi
- Two algorithms for constructing a Delaunay triangulation
- Two-Dimensional Voronoi Diagrams in the L p -Metric
- Voronoui Diagrams in $L_1 (L_\infty )$ Metrics with 2-Dimensional Storage Applications
- Generalization of Voronoi Diagrams in the Plane
- Use of Steiner's problem in suboptimal routing in rectilinear metric
- An O(n log n) algorithm for suboptimal rectilinear Steiner trees
- An O ( n log n ) Algorithm for Rectilinear Minimal Spanning Trees
This page was built for publication: An O(n log n) plane-sweep algorithm for \(L_ 1\) and \(L_{\infty}\) Delaunay triangulations
