Forest-like abstract Voronoi diagrams in linear time

DOI10.1016/J.COMGEO.2017.06.013MaRDI QIDQ1699286zbMATH OpenOpenAlexFDO

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

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)

Recommendations

• scientific article; zbMATH DE number 18530
• scientific article; zbMATH DE number 4098181
• On the construction of abstract Voronoi diagrams
• Abstract Voronoi diagrams from closed bisecting curves
• scientific article; zbMATH DE number 403949

Cites work

• scientific article; zbMATH DE number 732977 (Why is no real title available?)
• scientific article; zbMATH DE number 1182913 (Why is no real title available?)
• scientific article; zbMATH DE number 1455125 (Why is no real title available?)
• scientific article; zbMATH DE number 1555916 (Why is no real title available?)
• A linear-time algorithm for computing the Voronoi diagram of a convex polygon
• Abstract Voronoi diagrams revisited
• Concrete and abstract Voronoi diagrams
• Finding Hamiltonian cycles in Delaunay triangulations is NP-complete
• Linear-time algorithms for the farthest-segment Voronoi diagram and related tree structures
• Randomized incremental construction of abstract Voronoi diagrams
• Voronoi diagrams and Delaunay triangulations

Cited in

(7)

• Abstract Voronoi-like graphs: extending Delaunay's theorem and applications
• On selecting a fraction of leaves with disjoint neighborhoods in a plane tree
• Deletion in Abstract Voronoi Diagrams in Expected Linear Time.
• Navigating Forest Straight-Line Programs in Constant Time
• scientific article; zbMATH DE number 1555916 (Why is no real title available?)
• Deletion in abstract Voronoi diagrams in expected linear time and related problems
• Linear-time algorithms for the farthest-segment Voronoi diagram and related tree structures

Describes a project that uses

Uses Software

• Voronoi

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

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