Deletion in Abstract Voronoi Diagrams in Expected Linear Time.

DOI10.4230/LIPICS.SOCG.2018.50zbMATH Open1489.68362OpenAlexW2962797788MaRDI QIDQ5115818FDOQ5115818

Kolja Junginger, Evanthia Papadopoulou

Publication date: 18 August 2020

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

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

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)

Cites Work

• Title not available (Why is that?)
• Concrete and abstract Voronoi diagrams
• The higher-order Voronoi diagram of line segments
• Title not available (Why is that?)
• Title not available (Why is that?)
• FURTHEST SITE ABSTRACT VORONOI DIAGRAMS
• Abstract Voronoi diagrams revisited
• A linear-time algorithm for computing the Voronoi diagram of a convex polygon
• Finding the medial axis of a simple polygon in linear time
• Randomized incremental construction of abstract Voronoi diagrams
• Title not available (Why is that?)
• On the complexity of higher order abstract Voronoi diagrams
• A randomized divide and conquer algorithm for higher-order abstract Voronoi diagrams
• Linear-Time Algorithms for the Farthest-Segment Voronoi Diagram and Related Tree Structures
• Title not available (Why is that?)
• An Efficient Randomized Algorithm for Higher-Order Abstract Voronoi Diagrams.

Cited In (2)

• Deletion in abstract Voronoi diagrams in expected linear time and related problems
• 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)