The Number of Lines Tangent to Arbitrary Convex Polyhedra in 3D

2 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée
4 ISA - Models, algorithms and geometry for computer graphics and vision
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We prove that the lines tangent to four possibly intersecting polytopes in $R3$ with $n$ edges in total form $\Theta(n^2)$ connected components. In the generic case, each connected component is a single line, but our result still holds for arbitrary degenerate scenes. This improves the previously known $O(n^3\log n)$ bound by Agarwal~\cite{A94}. More generally, we show that a set of $k$ polytopes with a total of $n$ edges admits, in the worse case, $\Theta(n^2k^2)$ connected components of lines tangent to any four of these polytopes.
keyword :
Type de document :
Communication dans un congrès
Symposium on Computational Geometry - SoCG'2004, Jun 2004, Brooklyn, NY, United States. ACM, pp.46 - 55, 2004, 〈10.1145/997817.997827〉

Littérature citée [12 références]

https://hal.inria.fr/inria-00103995
Contributeur : Sylvain Lazard <>
Soumis le : lundi 19 novembre 2007 - 17:29:41
Dernière modification le : samedi 27 janvier 2018 - 01:31:36
Document(s) archivé(s) le : mardi 6 avril 2010 - 18:33:07

Fichier

p135-lazard.pdf
Fichiers produits par l'(les) auteur(s)

Citation

Hervé Brönnimann, Olivier Devillers, Vida Dujmovic, Hazel Everett, Marc Glisse, et al.. The Number of Lines Tangent to Arbitrary Convex Polyhedra in 3D. Symposium on Computational Geometry - SoCG'2004, Jun 2004, Brooklyn, NY, United States. ACM, pp.46 - 55, 2004, 〈10.1145/997817.997827〉. 〈inria-00103995〉

Métriques

Consultations de la notice

314

Téléchargements de fichiers