HAL - INRIA :: [inria-00413159, version 1] An Algorithm for Constructing the Convex Hull of a Set of Spheres in Dimension d

inria-00413159, version 1

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

Jean-Daniel Boissonnat () ¹, André Cerezo^a^, 1, Olivier Devillers () ¹, Jacqueline Duquesne ¹, Mariette Yvinec () ^1, 2

Computational Geometry 6 (1996) 123-130

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

a – Université de Nice
1 : PRISME (INRIA Sophia Antipolis)
INRIA
2 : Laboratoire d'Informatique, Signaux, et Systèmes de Sophia-Antipolis (I3S)
Université de Nice Sophia Antipolis (UNS) – CNRS : UMR7271

inria-00413159, version 1
http://hal.inria.fr/inria-00413159
oai: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

Voir la fiche détaillée

Documents associés

PDF :

Exporter

Bibtex EndNote TEI RefWorks

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="article"><head>Articles dans des revues avec comité de lecture</head>
<biblStruct type="article" xml:id="inria-00413159"><analytic>
<author><persName><forename>Jean-Daniel</forename><surname>Boissonnat</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Sophia Antipolis</orgName>
<orgName type="team">PRISME</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
</affiliation>
</author>
<author><persName><forename>André</forename><surname>Cerezo</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Sophia Antipolis</orgName>
<orgName type="team">PRISME</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
</affiliation>
</author>
<author><persName><forename>Olivier</forename><surname>Devillers</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Sophia Antipolis</orgName>
<orgName type="team">PRISME</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
</affiliation>
</author>
<author><persName><forename>Jacqueline</forename><surname>Duquesne</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Sophia Antipolis</orgName>
<orgName type="team">PRISME</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
</affiliation>
</author>
<author><persName><forename>Mariette</forename><surname>Yvinec</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Sophia Antipolis</orgName>
<orgName type="team">PRISME</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">I3S</orgName>
<orgName type="team">Laboratoire d'Informatique, Signaux, et Systèmes de Sophia-Antipolis</orgName>
<country>FR</country>
<orgName type="institution">Université de Nice Sophia Antipolis (UNS)</orgName>
<orgName type="institution">CNRS : UMR7271</orgName>
</affiliation>
</author>
<title type="main" level="a">An Algorithm for Constructing the Convex Hull of a Set of Spheres in Dimension d</title></analytic><monogr><title level="j" type="main">Computational Geometry</title><imprint><publisher>Elsevier</publisher><biblScope type="publicationDate">1996-00-00</biblScope><biblScope type="vol">6</biblScope><biblScope type="pp">123-130</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/inria-00413159</idno><idno type="HALFile">http://hal.inria.fr/inria-00413159/PDF/bcddy-acchs-96.pdf</idno></biblStruct>
</listBibl>
</listBibl>