Sublinear Explicit Incremental Planar Voronoi Diagrams

2020/07/03 by Arseneva, Elena, Iacono, John, Koumoutsos, Grigorios +2
#68U05 #Computational Geometry (cs.CG) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2007.01686

Abstract

A data structure is presented that explicitly maintains the graph of a Voronoi diagram of N point sites in the plane or the dual graph of a convex hull of points in three dimensions while allowing insertions of new sites/points. Our structure supports insertions in O (N^3/4) expected amortized time, where O suppresses polylogarithmic terms. This is the first result to achieve sublinear time insertions; previously it was shown by Allen et al. that Θ(√(N)) amortized combinatorial changes per insertion could occur in the Voronoi diagram but a sublinear-time algorithm was only presented for the special case of points in convex position.

Related

• Incremental Voronoi Diagrams
• Deletion in abstract Voronoi diagrams in expected linear time and related problems
• A New Approach to Output-Sensitive Voronoi Diagrams and Delaunay Triangulations
• An Optimal Algorithm for Higher-Order Voronoi Diagrams in the Plane: The Usefulness of Nondeterminism
• Data Structures for Halfplane Proximity Queries and Incremental Voronoi\n Diagrams