On computing Voronoi diagrams by divide-prune-and-conquer
Nancy M. Amato, Edgar A. Ramos · 1996
Using a divide, prune, and conquer approach based on geometric partitioning, we obtain: (1) An output sensitive algorithm for computing a weighted Voronoi diagram in IL4 (the projection of certain polyhedra in R5) that runs in time O ((n + f) log3 f) where n is the number of sites and f is the number of output cells;