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

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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/inria-00103995
Contributor : Sylvain Lazard <>
Submitted on : Monday, November 19, 2007 - 5:29:41 PM
Last modification on : Saturday, January 27, 2018 - 1:31:36 AM
Long-term archiving on : Tuesday, April 6, 2010 - 6:33:07 PM

File

p135-lazard.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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

Share

Metrics

Record views

470

Files downloads

129