inria-00103995, version 1
The Number of Lines Tangent to Arbitrary Convex Polyhedra in 3D
Hervé Brönnimann a, 1Olivier Devillers
b, 2Vida Dujmovic c, 3Hazel Everett d, 4Marc Glisse d, 4Xavier Goaoc b, 4Sylvain Lazard b, 4Hyeon-Suk Na e, 5Sue Whitesides c, 3
ACM Symposium on Computational Geometry - SoCG'2004 (2004) 46 - 55
Résumé : 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.
- a – Polytechnic University of New York
- b – INRIA
- c – MCGILL UNIVERSITY
- d – Université Nancy II
- e – 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 : ISA (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
- Domaine : Informatique/Géométrie algorithmique
- Mots-clés : computational geometry – 3d visibility || géométrie algoritmique – visibilité 3d
- Référence interne : A04-R-022 || bronnimann04a
- Commentaire : Colloque avec actes et comité de lecture. internationale.
- inria-00103995, version 1
- http://hal.inria.fr/inria-00103995
- oai:hal.inria.fr:inria-00103995
- Contributeur : Sylvain Lazard
- Soumis le : Lundi 19 Novembre 2007, 17:29:41
- Dernière modification le : Dimanche 20 Décembre 2009, 16:29:16
Documents associés
Exporter