Sorting helps for Voronoi diagrams

DOI10.1007/BF02526034zbMath0868.68109MaRDI QIDQ1355725

Steven Fortune, L. Paul Chew

Publication date: 1997

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

Voronoi diagramsDelaunay triangulationsconvex distance function

Mathematics Subject Classification ID

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

Related Items (7)

Finding the k smallest spanning trees ⋮ Sorting helps for Voronoi diagrams ⋮ Fine-grain discrete Voronoi diagram algorithms in \(L_1\) and \(L_\infty\) norms ⋮ On the angle restricted nearest neighbor problem ⋮ Finding the \(k\) smallest spanning trees ⋮ Fast geometric approximation techniques and geometric embedding problems ⋮ Computing hereditary convex structures

Cites Work

• Unnamed Item
• Unnamed Item
• A sweepline algorithm for Voronoi diagrams
• Sorting helps for Voronoi diagrams
• There are planar graphs almost as good as the complete graph
• A priority queue in which initialization and queue operations takeO(loglogD) time
• Two-Dimensional Voronoi Diagrams in the L _p -Metric
• Voronoui Diagrams in $L_1 (L_\infty )$ Metrics with 2-Dimensional Storage Applications
• Lower Bounds for Algebraic Computation Trees of Functions with Finite Domains
• Finding Minimum Spanning Trees
• Design and implementation of an efficient priority queue

This page was built for publication: Sorting helps for Voronoi diagrams