Lines and free line segments Tangent to Arbitrary Three-dimensional Convex Polyhedra - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue SIAM Journal on Computing Année : 2007

Lines and free line segments Tangent to Arbitrary Three-dimensional Convex Polyhedra

Olivier Devillers
Vida Dujmovic
  • Fonction : Auteur
  • PersonId : 835676
Sue Whitesides
  • Fonction : Auteur
  • PersonId : 835678

Résumé

Motivated by visibility problems in three dimensions, we investigate the complexity and construction of the set of tangent lines in a scene of three-dimensional polyhedra. We prove that the set of lines tangent to four possibly intersecting convex polyhedra in $\Real^3$ with a total of $n$ edges consists of $\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 arbitrarily 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 at least four polytopes. Furthermore, these bounds also hold for possibly occluded lines rather than maximal free line segments. Finally, we present a $O(n^2 k^2 \log n)$ time and $O(nk^2)$ space algorithm that, given a scene of $k$ possibly intersecting convex polyhedra, computes all the \emph{minimal} free line segments that are tangent to any four of the polytopes and are isolated transversals to the set of edges they intersect; in particular, we compute at least one line segment per connected component of tangent lines.
Fichier principal
Vignette du fichier
SIAM_final.pdf (266.71 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00103916 , version 1 (19-11-2007)

Identifiants

Citer

Hervé Brönnimann, Olivier Devillers, Vida Dujmovic, Hazel Everett, Marc Glisse, et al.. Lines and free line segments Tangent to Arbitrary Three-dimensional Convex Polyhedra. SIAM Journal on Computing, 2007, 37 (2), pp.522-551. ⟨10.1137/S0097539705447116⟩. ⟨inria-00103916⟩
315 Consultations
282 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More