Title: Deletion in Abstract Voronoi Diagrams in Expected Linear Time and Related Problems
Abstract: Abstract Updating an abstract Voronoi diagram in linear time, after deletion of one site, has been an open problem in a long time; similarly, for any concrete Voronoi diagram of generalized (non-point) sites. In this paper we present a simple, expected linear-time algorithm to update an abstract Voronoi diagram after deletion of one site. To achieve this result, we use the concept of a Voronoi-like diagram, a relaxed Voronoi structure of independent interest. Voronoi-like diagrams serve as intermediate structures, which are considerably simpler to compute, thus, making an expected linear-time construction possible. We formalize the concept and prove that it is robust under insertion, therefore, enabling its use in incremental constructions. The time-complexity analysis introduces a variant to backwards analysis, which is applicable to order-dependent structures. We further extend the technique to compute in expected linear time: the order- $$(k\,{+}\,1)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>k</mml:mi> <mml:mspace /> <mml:mo>+</mml:mo> <mml:mspace /> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> subdivision within an order- k Voronoi region, and the farthest abstract Voronoi diagram, after the order of its regions at infinity is known.