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 _∞ metric, and also under a simplicial distance function, are both shown to be \(\Theta(n^{\lceil d/2 \rceil})\) . 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^{\left\lceil d/2 \right\rceil})\) , for d ≥ 1 , and it improves to \(\Theta(n^{\left\lfloor d/2 \right\rfloor})\) , for d ≥ 2 , if all the hypercubes have the same size. Under the L ₁ metric, the maximum complexity of the Voronoi diagram of a set of n points in general position in R ³ 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 _∞ distance function. Their expected randomized complexities are \(O(n \log n + n ^{\left\lceil d/2 \right\rceil})\) for simplicial diagrams and \(O(n ^{\left\lceil d/2 \right\rceil} \log ^{d-1} n)\) for L _∞ -diagrams.

Authors and Affiliations

1. INRIA, 2004 Route des Lucioles, B.P. 109, 06561 Valbonne cedex, France {Jean-Daniel.Boissonnat,Mariette.Yvinec}@sophia.inria.fr , , , , , , FR

   J.-D. Boissonnat & M. Yvinec

2. School of Mathematical Sciences, Tel Aviv University, Tel Aviv 69978, Israel , , , , , , IL

   M. Sharir

3. Courant Institute of Mathematical Sciences, New York University, New York, NY 10012, USA {sharir,mia}@math.tau.ac.il , , , , , , US

   B. Tagansky

Received July 31, 1995, and in revised form September 9, 1997.

Reprints and permissions