Voronoi Diagrams in Higher Dimensions under Certain Polyhedral Distance Functions - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport Année : 1995

Voronoi Diagrams in Higher Dimensions under Certain Polyhedral Distance Functions

Jean-Daniel Boissonnat
  • Fonction : Auteur
  • PersonId : 830857
Micha Sharir
  • Fonction : Auteur
Boaz Tagansky
  • Fonction : Auteur
Mariette Yvinec

Résumé

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.

Domaines

Autre [cs.OH]
Fichier principal
Vignette du fichier
RR-2629.pdf (480.75 Ko) Télécharger le fichier

Dates et versions

inria-00074058 , version 1 (24-05-2006)

Identifiants

  • HAL Id : inria-00074058 , version 1

Citer

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⟩
105 Consultations
183 Téléchargements

Partager

Gmail Facebook X LinkedIn More