The Number of Lines Tangent to Arbitrary Convex Polyhedra in 3D - Archive ouverte HAL Access content directly
Conference Papers Year : 2004

## The Number of Lines Tangent to Arbitrary Convex Polyhedra in 3D

(1) , (2) , (3) , (4) , (4) , (4) , (4) , (5) , (3)
1
2
3
4
5
Hervé Brönnimann
• Function : Author
Olivier Devillers
Vida Dujmovic
• Function : Author
Hazel Everett
• Function : Author
• PersonId : 830545
Marc Glisse
Xavier Goaoc
Sylvain Lazard
Hyeon-Suk Na
• Function : Author
Sue Whitesides
• Function : Author

#### Abstract

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.

### Dates and versions

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

### Identifiers

• HAL Id : inria-00103995 , version 1
• DOI :

### Cite

Hervé Brönnimann, Olivier Devillers, Vida Dujmovic, Hazel Everett, Marc Glisse, et al.. The Number of Lines Tangent to Arbitrary Convex Polyhedra in 3D. Proceedings of the 20th Annual Symposium on Computational Geometry, Jun 2004, Brooklyn, NY, United States. pp.46 - 55, ⟨10.1145/997817.997827⟩. ⟨inria-00103995⟩

### Export

BibTeX TEI Dublin Core DC Terms EndNote Datacite

287 View