On the complexity of higher order abstract Voronoi diagrams

DOI10.1016/j.comgeo.2015.04.008zbMath1396.65033OpenAlexW279200107MaRDI QIDQ2354919

Panagiotis Cheilaris, Maksym Zavershynskyi, Evanthia Papadopoulou, Chih-Hung Liu, Cecilia Bohler, Rolf Klein

Publication date: 27 July 2015

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

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

zbMATH Keywords

computational geometryVoronoi diagramsabstract Voronoi diagramsdistance problemshigher order Voronoi diagrams

Mathematics Subject Classification ID

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

Related Items

A randomized divide and conquer algorithm for higher-order abstract Voronoi diagrams ⋮ Degree distributions in \(AB\) random geometric graphs ⋮ An efficient randomized algorithm for higher-order abstract Voronoi diagrams ⋮ Deletion in abstract Voronoi diagrams in expected linear time and related problems ⋮ The impact of heterogeneity and geometry on the proof complexity of random satisfiability ⋮ Voronoi Diagram for Convex Polygonal Sites with Convex Polygon-Offset Distance Function ⋮ Deletion in Abstract Voronoi Diagrams in Expected Linear Time. ⋮ Nearly Optimal Planar $k$ Nearest Neighbors Queries under General Distance Functions

Uses Software

• Voronoi

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Randomized incremental construction of abstract Voronoi diagrams
• On the construction of abstract Voronoi diagrams
• Abstract Voronoi diagrams revisited
• The number of small semispaces of a finite set of points in the plane
• On the combinatorial classification of nondegenerate configurations in the plane
• Concrete and abstract Voronoi diagrams
• Casting a polyhedron with directional uncertainty
• Quickest paths, straight skeletons, and the city Voronoi diagram
• Applications of random sampling in computational geometry. II
• Voronoi Diagrams and Delaunay Triangulations
• A Randomized Divide and Conquer Algorithm for Higher-Order Abstract Voronoi Diagrams
• An Output-Sensitive Approach for the L 1/L  ∞  k-Nearest-Neighbor Voronoi Diagram
• On k-Nearest Neighbor Voronoi Diagrams in the Plane
• FURTHEST SITE ABSTRACT VORONOI DIAGRAMS
• On the Complexity of Higher Order Abstract Voronoi Diagrams
• VORONOI DIAGRAMS FOR A TRANSPORTATION NETWORK ON THE EUCLIDEAN PLANE
• Algorithms - ESA 2003