Deletion in Abstract Voronoi Diagrams in Expected Linear Time.

DOI10.4230/LIPICS.SOCG.2018.50MaRDI QIDQ5115818zbMATH OpenOpenAlexFDO

Authors Kolja Junginger, Evanthia Papadopoulou

Publication date 18 August 2020

Full work available at URL https://doi.org/10.4230/LIPIcs.SoCG.2018.50

zbMATH Keywords

abstract Voronoi diagramlinear-time algorithmrandomized incremental algorithmupdate after deletion

Mathematics Subject Classification ID

Randomized algorithms (68W20) Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Deletion in abstract Voronoi diagrams in expected linear time and related problems
• Higher-dimensional Voronoi diagrams in linear expected time
• Forest-like abstract Voronoi diagrams in linear time
• scientific article; zbMATH DE number 7651184
• scientific article; zbMATH DE number 1555916
• Tight running time lower bounds for vertex deletion problems
• On the complexity of higher order abstract Voronoi diagrams
• On the complexity of higher order abstract Voronoi diagrams
• Approximation and kernelization for chordal vertex deletion
• Approximation and kernelization for chordal vertex deletion

Cites work

• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• scientific article; zbMATH DE number 732977 (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?)
• scientific article; zbMATH DE number 1433426 (Why is no real title available?)
• A linear-time algorithm for computing the Voronoi diagram of a convex polygon
• A randomized divide and conquer algorithm for higher-order abstract Voronoi diagrams
• Abstract Voronoi diagrams revisited
• An efficient randomized algorithm for higher-order abstract Voronoi diagrams
• Concrete and abstract Voronoi diagrams
• FURTHEST SITE ABSTRACT VORONOI DIAGRAMS
• Finding the medial axis of a simple polygon in linear time
• Linear-time algorithms for the farthest-segment Voronoi diagram and related tree structures
• On the complexity of higher order abstract Voronoi diagrams
• Randomized incremental construction of abstract Voronoi diagrams
• The higher-order Voronoi diagram of line segments

Cited in

(4)

• Deletion in abstract Voronoi diagrams in expected linear time and related problems
• Dynamic construction of abstract Voronoi diagrams
• Abstract Voronoi-like graphs: extending Delaunay's theorem and applications
• On selecting a fraction of leaves with disjoint neighborhoods in a plane tree

This page was built for publication: Deletion in Abstract Voronoi Diagrams in Expected Linear Time.

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