Voronoi diagrams in higher dimensions under certain polyhedral distance functions

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 R-d, the maximum complexity of its Voronoi diagram under the L-infinity metric, and also under a simplicial distance function, are both shown to be Theta(n ([d/2])). The upper bound for the case of the L, metric follows from a new upper bound, also proved in this paper, on the maximum complexity of the union of n axis-parallel hypercubes in R-d. This complexity is Theta(n ([d/2])), for d greater than or equal to 1, and it improves to Theta(n ([d/2])), for d greater than or equal to 2, if all the hypercubes have the same size. Under the L-1 metric, the maximum complexity of the Voronoi diagram of a set of n points in general position in R-3 is shown to be Theta(n(2)). 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. (This increase does not occur with an appropriate modification of the diagram definition.) Finally, on-line algorithms are proposed for computing the Voronoi diagram of n points in R-d under a simplicial or L-infinity distance function. Their expected randomized complexities are O(n log n + n([d/2])) for simplicial diagrams and O(n ([d/2]) log(d-1) n) for L-infinity-diagrams.