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).
Domains
Computational Geometry [cs.CG]
Origin : Files produced by the author(s)