Deletion in abstract Voronoi diagrams in expected linear time and related problems

DOI10.1007/S00454-022-00463-ZarXiv1803.05372OpenAlexW3116781849MaRDI QIDQ6045784

Evanthia Papadopoulou, Kolja Junginger

Publication date: 12 May 2023

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1803.05372

zbMATH Keywords

abstract Voronoi diagrambackwards analysislinear-time algorithmhigher-order Voronoi diagramrandomized incremental constructionfarthest Voronoi diagramsite-deletion

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• Unnamed Item
• 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 the medial axis of a simple polygon in linear time
• Forest-like abstract Voronoi diagrams in linear time
• The Hausdorff Voronoi diagram of point clusters in the plane
• On the complexity of higher order abstract Voronoi diagrams
• An efficient randomized algorithm for higher-order abstract Voronoi diagrams
• Vertex Deletion for 3D Delaunay Triangulations
• Voronoi Diagrams and Delaunay Triangulations
• ON THE FARTHEST LINE-SEGMENT VORONOI DIAGRAM
• FURTHEST SITE ABSTRACT VORONOI DIAGRAMS
• Deletion in Abstract Voronoi Diagrams in Expected Linear Time.

This page was built for publication: Deletion in abstract Voronoi diagrams in expected linear time and related problems