×

Voronoi diagrams in higher dimensions under certain polyhedral distance functions. (English) Zbl 0897.68113

Summary: The paper bounds the combinatorial complexity of the Voronoi diagram of a set of points under certain polyhedral distance functions. Specifically, if \({\mathcal S}\) is a set of \(n\) points in general position in \(\mathbb{R}^d\), the maximum complexity of its Voronoi diagram under the \(L_\infty\) 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_\infty\) 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 \(\mathbb{R}^d\). This complexity is \(\Theta(n^{\lceil d/2\rceil})\), for \(d\geq 1\), and it improves to \(\Theta(n^{\lfloor d/2\rfloor})\), for \(d\geq 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 \(\mathbb{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 \(\mathbb{R}^d\) under a simplicial or \(L_\infty\) distance function. Their expected randomized complexities are \(O(n\log n+ n^{\lceil d/2\rceil})\) for simplicial diagrams and \(O(n^{\lceil d/2\rceil}\log^{d- 1}n)\) for \(L_\infty\)-diagrams.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)

Keywords:

Voronoi diagram
PDFBibTeX XMLCite
Full Text: DOI