The number of lines tangent to arbitrary convex polyhedra in 3D
Hervé Brönnimann, Olivier Devillers, Vida Dujmović, Hazel Everett, Marc Glisse, Xavier Goaoc, Sylvain Lazard, Hyeonseok Na, Sue H. Whitesides · 2004
We prove that the lines tangent to four possibly intersecting convex polyhedra in ℝ3 with n edges in total form Θ(n2) connected components in the worst case. In the generic case, each connected component is a single line, but our result still holds for arbitrary degenerate scenes. More generally, we show that a set of kconvex polyhedra with a total of n edges admits, in the worst case, Θ(n2k2)connected components of (possibly occluded) lines tangent to any four of these polyhedra. We also show a lower bound of Ω(n2k2) on the number of non-occluded maximal line segments tangent to any four of these k convex polyhedra.