DUQUESNE , Jacqueline

Disponible dans les fichiers attachés à ce document

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