Deletion in Abstract Voronoi Diagrams in Expected Linear Time.

DOI10.4230/LIPIcs.SoCG.2018.50zbMath1489.68362OpenAlexW2962797788MaRDI QIDQ5115818

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

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

Related Items

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The higher-order Voronoi diagram of line segments
• A randomized divide and conquer algorithm for higher-order abstract Voronoi diagrams
• 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 the medial axis of a simple polygon in linear time
• On the complexity of higher order abstract Voronoi diagrams
• An Efficient Randomized Algorithm for Higher-Order Abstract Voronoi Diagrams.
• Linear-Time Algorithms for the Farthest-Segment Voronoi Diagram and Related Tree Structures
• FURTHEST SITE ABSTRACT VORONOI DIAGRAMS