ISSN:
1432-0444
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract. 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 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 ∞ 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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/PL00009366
Permalink
