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).
Document type :
Journal articles
Complete list of metadatas

https://hal.inria.fr/inria-00413159
Contributor : Olivier Devillers <>
Submitted on : Thursday, September 3, 2009 - 2:15:56 PM
Last modification on : Wednesday, March 7, 2018 - 10:13:04 AM
Long-term archiving on : Tuesday, June 15, 2010 - 11:07:51 PM

File

bcddy-acchs-96.pdf
Files produced by the author(s)

Identifiers

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. ⟨10.1016/0925-7721(95)00024-0⟩. ⟨inria-00413159⟩

Share

Metrics

Record views

851

Files downloads

261