Output sensitive and dynamic constructions of higher order voronoi diagrams and levels in arrangements

摘要

We give efficient, output sensitive algorithms to construct Voronoi diagrams of order one to k of a given collection of sites in Rd and levels of order one to k in a nonredundant arrangement of hyperplanes in Rd (an arrangement is called nonredundant if every hyperplane in it supports the convex polytope of the arrangement surrounding the origin). We also give efficient dynamic algorithms for the same problems that allow the user to add or delete an object-the object being a site in the case of Voronoi diagrams and a nonredundant hyperplane in the case of levels.