An Algorithm for Constructing the Convex Hull of a Set of Spheres in Dimension d
Résumé
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).
Domaines
Géométrie algorithmique [cs.CG]
Origine : Fichiers produits par l'(les) auteur(s)