On the Number of Maximal Free Line Segments Tangent to Arbitrary Three-dimensional Convex Polyhedra

2 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée
4 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We prove that the lines tangent to four possibly intersecting convex polyhedra in $^3$ with $n$ edges in total form $\Theta(n^2)$ connected components in the worst case. In the generic case, each connected component is a single line, but our result still holds for arbitrary degenerate scenes. More generally, we show that a set of $k$ possibly intersecting convex polyhedra with a total of $n$ edges admits, in the worst case, $\Theta(n^2k^2)$ connected components of maximal free line segments tangent to any four of the polytopes. This bound also holds for the number of connected components of possibly occluded lines tangent to any four of the polytopes.
Keywords :
Type de document :
Rapport
[Research Report] RR-5671, INRIA. 2005
Domaine :

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

https://hal.inria.fr/inria-00071226
Contributeur : Rapport de Recherche Inria <>
Soumis le : mardi 23 mai 2006 - 14:43:37
Dernière modification le : jeudi 17 janvier 2019 - 15:58:10
Document(s) archivé(s) le : dimanche 4 avril 2010 - 22:02:10

Identifiants

• HAL Id : inria-00071226, version 1

Citation

Hervé Brönnimann, Olivier Devillers, Vida Dujmovic, Hazel Everett, Marc Glisse, et al.. On the Number of Maximal Free Line Segments Tangent to Arbitrary Three-dimensional Convex Polyhedra. [Research Report] RR-5671, INRIA. 2005. 〈inria-00071226〉

Métriques

Consultations de la notice

437

Téléchargements de fichiers