An Improved Algorithm for Constructing kth-Order Voronoi Diagrams

DOI10.1109/TC.1987.5009474MaRDI QIDQ3799631zbMATH OpenFDO

Authors Bernard Chazelle, Herbert Edelsbrunner

Publication date 1987

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

Full work available at URL https://doi.org/10.1109/TC.1987.5009474

zbMATH Keywords

arrangements of lines and planescomputational geometryEuclidean planegeometric transformsmaintenance of convex hullsprojective spaceVoronoi diagram

Mathematics Subject Classification ID

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

Recommendations

• On k-Nearest Neighbor Voronoi Diagrams in the Plane
• A new duality result concerning Voronoi diagrams
• A new duality result concerning Voronoi diagrams
• scientific article; zbMATH DE number 219275
• A SIMPLE ON-LINE RANDOMIZED INCREMENTAL ALGORITHM FOR COMPUTING HIGHER ORDER VORONOI DIAGRAMS

Cited in

(22)

• Iterated nearest neighbors and finding minimal polytopes
• Higher order mobile coverage control with applications to clustering of discrete sets
• The \(k\)-nearest-neighbor Voronoi diagram revisited
• Voronoi diagrams over dynamic scenes
• An efficient randomized algorithm for higher-order abstract Voronoi diagrams
• Computing closest and farthest points for a query segment
• The higher-order Voronoi diagram of line segments
• A randomized divide and conquer algorithm for higher-order abstract Voronoi diagrams
• A SIMPLE ON-LINE RANDOMIZED INCREMENTAL ALGORITHM FOR COMPUTING HIGHER ORDER VORONOI DIAGRAMS
• Round-trip Voronoi diagrams and doubling density in geographic networks
• A randomized divide and conquer algorithm for higher-order abstract Voronoi diagrams
• Higher Order Voronoi Diagrams and Distance Functions in Art and Visualization
• On k-Nearest Neighbor Voronoi Diagrams in the Plane
• scientific article; zbMATH DE number 219275 (Why is no real title available?)
• scientific article; zbMATH DE number 2102914 (Why is no real title available?)
• Higher Order Voronoi Diagrams of Segments for VLSI Critical Area Extraction
• Nearly Optimal Planar k Nearest Neighbors Queries under General Distance Functions
• A new duality result concerning Voronoi diagrams
• A new duality result concerning Voronoi diagrams
• The k-centrum straight-line location problem
• Finding an Euclidean anti-\(k\)-centrum location of a set of points
• Order-k Voronoi diagrams of sites with additive weights in the plane

This page was built for publication: An Improved Algorithm for Constructing kth-Order Voronoi Diagrams

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