HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Reports

Voronoi Diagrams in Higher Dimensions under Certain Polyhedral Distance Functions

Abstract : The paper bounds the combinatorial complexity of the Voronoi diagram of a set of points under certain polyhedral distance functions. Specifically, if $ß$ is a set of $n$ points in general position in $\Ee maximum complexity of its Voronoi diagram under the $\Linf$ 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 $\Linf$ 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 $\E complexity isof $\Theta(n^{\ceil{d/2}})$, for $d \ge 1$, and it improves to $\Theta(n^{\floor{d/2}})$, for $d \ge 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 $\Eown to be d $\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. Finally, on-line algorithms are proposed for computing the Voronoi diagram of $n$ points in $\E under a simplicial or $\Linf$ distance function. Their randomized complexities are $O(n \log n + n ^{\ceil{d/2}})$ for simplicial diagrams and $O(n ^{\ceil{d/2}} \log ^{d-1} n)$ for $\Linf$-diagrams.
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00074058
Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 2:24:18 PM
Last modification on : Friday, February 4, 2022 - 3:18:46 AM
Long-term archiving on: : Thursday, March 24, 2011 - 2:05:34 PM

Identifiers

  • HAL Id : inria-00074058, version 1

Collections

Citation

Jean-Daniel Boissonnat, Micha Sharir, Boaz Tagansky, Mariette Yvinec. Voronoi Diagrams in Higher Dimensions under Certain Polyhedral Distance Functions. RR-2629, INRIA. 1995. ⟨inria-00074058⟩

Share

Metrics

Record views

95

Files downloads

170