Deletion in Abstract Voronoi Diagrams in Expected Linear Time and Related Problems

Area of Science:

• Computational Geometry
• Algorithms and Data Structures

Background:

• Updating abstract Voronoi diagrams after site deletion is a long-standing open problem.
• Existing methods for generalized Voronoi diagrams are often inefficient.

Purpose of the Study:

• To present a simple, expected linear-time algorithm for updating abstract Voronoi diagrams after single site deletion.
• To introduce and utilize Voronoi-like diagrams as a key component for efficient updates.

Main Methods:

• Development of Voronoi-like diagrams as relaxed, simpler intermediate structures.
• Formalization and proof of robustness of Voronoi-like diagrams under insertion.
• Application of a variant of backwards analysis for time-complexity analysis of order-dependent structures.

Main Results:

• An expected linear-time algorithm for updating abstract Voronoi diagrams after site deletion.
• Demonstration of Voronoi-like diagrams' utility in incremental constructions.
• Extension of the technique to compute order-k subdivisions and farthest abstract Voronoi diagrams in expected linear time.

Conclusions:

• The proposed method provides an efficient solution to a previously open problem in computational geometry.
• Voronoi-like diagrams are a valuable tool for simplifying complex geometric structures and enabling faster algorithms.
• The developed techniques have broader applicability in the analysis of order-dependent data structures.