On the number of lines tangent to arbitrary polytopes in R³

• Version appeared in SoCG'04.

Abstract: We prove that the lines tangent to four possibly intersecting convex polyhedra in R³ with n edges in total form Theta(n2) connected components in the worst case. In the generic case, each connected component is a single line, but out result still holds for arbitrary degenerate cases. More generally, we show that a set of k convex polyhedra with a total of n edges admits, in the worst case, Theta(n2k2) connected components of (possibly occluded) lines tangent to any four of these polyhedra. We also show a lower boud of Omega(n2k2) on the number of non-occluded maximal line segments tangent to any four of these k convex polyhedra.

Related publications

• On the Number of Lines Tangent to Four Convex Polyhedra, with Olivier Devillers, Vida Dujmovic, Hazel Everett, Marc Glisse, Xavier Goaoc, Sylvain Lazard, Heon-Suk Na, and Sue Whitesides. CCCG'02.
• Transversals to line segments in R³, with Hazel Everett, Sylvain Lazard, Frank Sottile and Sue Whitesides. CCCG'03.
• On the number of lines tangent to four trianggles, with Olivier Devillers, Sylvain Lazard, Frank Sottile, and Sue Whitesides. CCCG'04.