Line Transversals of Convex Polyhedra in ℝ3
Haim Y. Kaplan, Natan Rubin, Micha Sharir · Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms · 2009
We establish a bound of O(n2k1+∊), for any ∊ > 0, on the combinatorial complexity of the set Ƭ of line transversals of a collection of k convex polyhedra in ℝ3 with a total of n facets, and present a randomized algorithm which computes the boundary of Ƭ in comparable expected time. Thus, when k ≪ n, the new bounds on the complexity (and construction cost) of Ƭ improve upon the previously best known bounds, which are nearly cubic in n. To obtain the above result, we study the set Ƭℓ0 of line transversals which emanate from a fixed line ℓ0, establish an almost tight bound of O(nk1+∊) on the complexity of Ƭℓ0, and provide a randomized algorithm which computes Ƭℓ0 in comparable expected time. Slightly improved combinatorial bounds for the complexity of Ƭℓ0, and comparable improvements in the cost of constructing this set, are established for two special cases, both assuming that the polyhedra of are pairwise disjoint: the case where ℓ0 is disjoint from the polyhedra of , and the case where the polyhedra of are unbounded in a direction parallel to ℓ0.