An Algorithm for Constructing the Convex Hull of a Set of Spheres in Dimension d

Abstract : We present an algorithm which computes the convex hull of a set of spheres in dimension d in time O(n^ceil(d/2)+n log n). It is worst case optimal in three dimensions and in even dimensions. The same method can also be used to compute the convex hull of a set of n homethetic objects of Ed. If the complexity of each object is constant, the time needed in the worst case is O(n^ceil(d/2)+n log n).
Type de document :
Article dans une revue
Computational Geometry, Elsevier, 1996, 6, pp.123-130
Liste complète des métadonnées

https://hal.inria.fr/inria-00413159
Contributeur : Olivier Devillers <>
Soumis le : jeudi 3 septembre 2009 - 14:15:56
Dernière modification le : mardi 20 octobre 2009 - 10:35:46
Document(s) archivé(s) le : mardi 15 juin 2010 - 23:07:51

Fichier

bcddy-acchs-96.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00413159, version 1

Collections

Citation

Jean-Daniel Boissonnat, André Cerezo, Olivier Devillers, Jacqueline Duquesne, Mariette Yvinec. An Algorithm for Constructing the Convex Hull of a Set of Spheres in Dimension d. Computational Geometry, Elsevier, 1996, 6, pp.123-130. <inria-00413159>

Partager

Métriques

Consultations de
la notice

300

Téléchargements du document

77