An Improved Algorithm for Constructing kth-Order Voronoi Diagrams

DOI10.1109/TC.1987.5009474zbMath0653.68033MaRDI QIDQ3799631

Bernard Chazelle, Herbert Edelsbrunner

Publication date: 1987

Published in: IEEE Transactions on Computers (Search for Journal in Brave)

zbMATH Keywords

projective spaceEuclidean planeVoronoi diagramcomputational geometrygeometric transformsarrangements of lines and planesmaintenance of convex hulls

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Convex sets in (2) dimensions (including convex curves) (52A10)

Related Items

Iterated nearest neighbors and finding minimal polytopes ⋮ Voronoi diagrams over dynamic scenes ⋮ A randomized divide and conquer algorithm for higher-order abstract Voronoi diagrams ⋮ A Randomized Divide and Conquer Algorithm for Higher-Order Abstract Voronoi Diagrams ⋮ An efficient randomized algorithm for higher-order abstract Voronoi diagrams ⋮ Round-Trip Voronoi Diagrams and Doubling Density in Geographic Networks ⋮ The \(k\)-centrum straight-line location problem ⋮ Higher Order Voronoi Diagrams of Segments for VLSI Critical Area Extraction ⋮ Higher order mobile coverage control with applications to clustering of discrete sets ⋮ A new duality result concerning Voronoi diagrams ⋮ Computing closest and farthest points for a query segment ⋮ Finding an Euclidean anti-\(k\)-centrum location of a set of points ⋮ Higher Order Voronoi Diagrams and Distance Functions in Art and Visualization ⋮ Nearly Optimal Planar $k$ Nearest Neighbors Queries under General Distance Functions ⋮ The \(k\)-nearest-neighbor Voronoi diagram revisited ⋮ The higher-order Voronoi diagram of line segments