Skip to Main content Skip to Navigation
Reports

On the combinatorial complexity of Euclidean Voronoi cells and convex hulls of d-dimensional spheres

Jean-Daniel Boissonnat 1 Menelaos I. Karavelas
1 PRISME - Geometry, Algorithms and Robotics
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : In this paper we show an equivalence relationship between additively weighted Voronoi cells in R [power d], power diagrams in R [power d] and convex hulls of spheres in R [power d]. An immediate consequence of this equivalence relationship is a tight bound on the complexity of : (1) a single additively weighted Voronoi cell in dimension d ; (2) the convex hull of a set of d-dimensional spheres. In particular, given a set of n spheres in dimension d, we show that the worst case complexity of both a single additively weighted Voronoi cell and the convex hull of the set of spheres is [THÊTA](n[power d/2]). The equivalence between additively weighted Voronoi cells and convex hulls of spheres permits us to compute a single additively weighted Voronoi cell in dimension d in worst case optimal time [OMICRON](n log n + n[power d/2]).
Document type :
Reports
Complete list of metadata

Cited literature [9 references]  Display  Hide  Download

https://hal.inria.fr/inria-00072084
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 7:45:30 PM
Last modification on : Saturday, January 27, 2018 - 1:30:57 AM
Long-term archiving on: : Sunday, April 4, 2010 - 10:52:22 PM

Identifiers

  • HAL Id : inria-00072084, version 1

Collections

Citation

Jean-Daniel Boissonnat, Menelaos I. Karavelas. On the combinatorial complexity of Euclidean Voronoi cells and convex hulls of d-dimensional spheres. RR-4504, INRIA. 2002. ⟨inria-00072084⟩

Share

Metrics

Record views

591

Files downloads

334