Voronoi diagrams in higher dimensions under certain polyhedral distance functions
Jean‐Daniel Boissonnat, Micha Sharir, Boaz Tagansky, Mariette Yvinec · 1995
The paper bounds the combinatorial complexity of the Voronoi diagram of a set of points under certain polyhedral distance functions.Specifically, if S is a set of n points in general position in Jf?-d, the complexity of its Voronoi diagram under the Lm metric, and also under a simplicial distance function, are both shown to be qn[dlzl ).The upper bound for the case of the Lm metric folIows from a new upper bound, also proved in this paper, on the complexity of the union of n axis-parallel hypercubes in Eld.This complexity is @(n ~d/21 ), for d > 1, and it improves to @(nld/2J ), for d ~2, if all the hypercubes have the same size.Under the L1 metric, the complexity of the Voronoi diagram of a set of n points in general position in IR3 is shown to be @(n2 ).We also show that the general position assumption is essential, and give examples where the complexity of the diagram increases significantly when the points are in degenerate configurations.