Published June 2004
| Version v1
Conference paper
The Number of Lines Tangent to Arbitrary Convex Polyhedra in 3D
Contributors
Others:
- Department of Computer and Information Science ; Polytechnic Institute of New York University
- Geometric computing (GEOMETRICA) ; Centre Inria d'Université Côte d'Azur (CRISAM) ; Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
- School of Computer Science [Ottawa] ; University of Ottawa [Ottawa]
- Models, algorithms and geometry for computer graphics and vision (ISA) ; INRIA Lorraine ; Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA) ; Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)
- School of Computing - Soongsil University, Séoul ; Soongsil University, Seoul
Description
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.
Abstract
Colloque avec actes et comité de lecture. internationale.Abstract
International audienceAdditional details
Identifiers
- URL
- https://inria.hal.science/inria-00103995
- URN
- urn:oai:HAL:inria-00103995v1
Origin repository
- Origin repository
- UNICA