VORONOI DIAGRAMS IN HIGHER DIMENSIONS UNDER CERTAIN POLYHEDRAL DISTANCE FUNCTIONS

The paper bounds the combinatorial complexity of the Voronoi diagram o f a set of points under certain polyhedral distance functions. Specifi cally, if S is a set of n points in general position in R-d, the maxim um 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 complexi ty 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 hyp ercubes have the same size. Under the L-1 metric, the maximum complexi ty 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 th e diagram increases significantly when the points are in degenerate co nfigurations. (This increase does not occur with an appropriate modifi cation of the diagram definition.) Finally, on-line algorithms are pro posed for computing the Voronoi diagram of n points in R-d under a sim plicial or L-infinity distance function. Their expected randomized com plexities are O(n log n + n([d/2])) for simplicial diagrams and O(n ([ d/2]) log(d-1) n) for L-infinity-diagrams.