I'll extend on my struggles to create sublinear algorithms that maintain the explicitly stored graph of a Voronoi diagram under insertion of a new point.