Dynamic Voronoi diagrams
Impa Bennuru Huliyappa Gowda, David G. Kirkpatrick, D. Lee, Amnon Naamad · IEEE Transactions on Information Theory · 1983
A new dynamizing technique is introduced wherebynpoint Voronoi diagrams (both closest and farthest point) can be updated inO(n)time per insertion or deletion, in the worst case. General properties of these dynamic Voronoi diagrams are explored including a storage/ deletion-time trade-off. In addition, their application to such problems as nearest neighbor search and the 2-minimum spanning circle problem is discussed.