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

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]).

Mots clés: COMPUTATIONAL GEOMETRY; COMBINATORIAL GEOMETRY; VORONOI DIAGRAMS; CONVEX HULLS; SPHERES

Domaines: Autre [cs.OH]

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⟩