inria-00103916, version 1
Lines and free line segments Tangent to Arbitrary Three-dimensional Convex Polyhedra
Hervé Bronnimann
1Olivier Devillers
a, 2Vida Dujmovic
3Hazel Everett
b, 4Marc Glisse
b, 4Xavier Goaoc
a, 4Sylvain Lazard
a, 4Hyeon-Suk Na
c, 5Sue Whitesides
6
SIAM Journal on Computing 37, 2 (2007) 522-551
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.
- a – INRIA
- b – Université Nancy II
- c – Soongsil University, Seoul
- 1 : Department of Computer and Information Science
- Polytechnic University of New York
- 2 : GEOMETRICA (INRIA Sophia Antipolis)
- INRIA
- 3 : School of Computer Science
- Carleton University
- 4 : VEGAS (INRIA Lorraine - LORIA)
- INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine
- 5 : School of Computing - Soongsil University, Séoul
- Soongsil University, Seoul
- 6 : School of Computer Science [Quebec] (SOCS)
- McGill University
- Domaine : Informatique/Géométrie algorithmique
- Mots-clés : computational geometry – 3D visibility – visibility complex – visual events
- inria-00103916, version 1
- http://hal.inria.fr/inria-00103916
- oai:hal.inria.fr:inria-00103916
- Contributeur : Sylvain Lazard
- Soumis le : Lundi 19 Novembre 2007, 17:38:14
- Dernière modification le : Jeudi 16 Avril 2009, 17:08:05






Documents associés
Exporter