Forest-like abstract Voronoi diagrams in linear time

DOI10.1016/j.comgeo.2017.06.013zbMath1396.65034OpenAlexW2728819971MaRDI QIDQ1699286

Rolf Klein, Chih-Hung Liu, Andrzej Lingas, Cecilia Bohler

Publication date: 19 February 2018

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

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

zbMATH Keywords

Voronoi diagramslinear-time algorithmsabstract Voronoi diagramsforest structuresgeneral distance

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Buildings and the geometry of diagrams (51E24)

Related Items (2)

On selecting a fraction of leaves with disjoint neighborhoods in a plane tree ⋮ Deletion in abstract Voronoi diagrams in expected linear time and related problems

Uses Software

• Voronoi

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Randomized incremental construction of abstract Voronoi diagrams
• Abstract Voronoi diagrams revisited
• A linear-time algorithm for computing the Voronoi diagram of a convex polygon
• Concrete and abstract Voronoi diagrams
• Finding Hamiltonian cycles in Delaunay triangulations is NP-complete
• Voronoi Diagrams and Delaunay Triangulations
• Linear-Time Algorithms for the Farthest-Segment Voronoi Diagram and Related Tree Structures

This page was built for publication: Forest-like abstract Voronoi diagrams in linear time