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

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 Connect in order to contact the contributor
Submitted on : Tuesday, May 23, 2006 - 7:45:30 PM
Last modification on : Friday, February 4, 2022 - 3:16:11 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

441

Files downloads

312