Incremental Voronoi?

[mbostock]

It’d be nice to be able to add a new point to an existing Voronoi diagram without having to start over from scratch. I’ve also been thinking about this divide-and-conquer algorithm as an alternative to Fortune’s:

http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/Voronoi/DivConqVor/divConqVor.htm