Output sensitive construction of levels and Voronoi diagrams in R d of order 1 to k
Ketan Mulmuley · 1990
We give efficient, output sensitive algorithms to construct levels of order 1 to k in a nonredundant arrangement of hyperplanes in R d, and Voronoi diagrams of order to 1 to k of a given collection of sites in R d.