A randomized divide and conquer algorithm for higher-order abstract Voronoi diagrams

DOI10.1016/j.comgeo.2016.08.004zbMath1355.65030OpenAlexW2508929803MaRDI QIDQ340524

Evanthia Papadopoulou, Chih-Hung Liu, Maksym Zavershynskyi, Cecilia Bohler

Publication date: 14 November 2016

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2016.08.004

zbMATH Keywords

Hausdorff metric\(k\) nearest neighborsabstract Voronoi diagramconvex distance metricdivide and conquergeometric randomized algorithmhigher-order Voronoi diagram

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Related Items (3)

An efficient randomized algorithm for higher-order abstract Voronoi diagrams ⋮ Deletion in Abstract Voronoi Diagrams in Expected Linear Time. ⋮ Nearly Optimal Planar $k$ Nearest Neighbors Queries under General Distance Functions

Cites Work

• Unnamed Item
• Unnamed Item
• The higher-order Voronoi diagram of line segments
• Randomized incremental construction of abstract Voronoi diagrams
• On the construction of abstract Voronoi diagrams
• Order-k Voronoi diagrams of sites with additive weights in the plane
• Abstract Voronoi diagrams revisited
• Triangulating a simple polygon in linear time
• Concrete and abstract Voronoi diagrams
• New applications of random sampling in computational geometry
• The \(k\)-nearest-neighbor Voronoi diagram revisited
• On the complexity of higher order abstract Voronoi diagrams
• A semidynamic construction of higher-order Voronoi diagrams and its randomized analysis
• Taking a Walk in a Planar Arrangement
• Higher Order City Voronoi Diagrams
• 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
• Linear-Time Algorithms for the Farthest-Segment Voronoi Diagram and Related Tree Structures
• An Improved Algorithm for Constructing kth-Order Voronoi Diagrams
• On k-Nearest Neighbor Voronoi Diagrams in the Plane
• Constructing Levels in Arrangements and Higher Order Voronoi Diagrams
• Random Sampling, Halfspace Range Reporting, and Construction of \lowercase$(\le k)$-Levels in Three Dimensions
• FURTHEST SITE ABSTRACT VORONOI DIAGRAMS
• Power Diagrams: Properties, Algorithms and Applications
• Optimal Deterministic Algorithms for 2-d and 3-d Shallow Cuttings
• Higher-Order Geodesic Voronoi Diagrams in a Polygonal Domain with Holes

This page was built for publication: A randomized divide and conquer algorithm for higher-order abstract Voronoi diagrams