נתן רובין

We establish a bound of O(n²k^1+ε), for any ε > 0, on the combinatorial complexity of the set T of line transversals of a collection P of k convex polyhedra in ℝ³ with a total of n facets, and present a randomized algorithm which computes the boundary of T in comparable expected time. Thus, when k ≪ n, the new bounds on the complexity (and construction cost) of T improve upon the previously best known bounds, which are nearly cubic in n. To obtain the above result, we study the set T _ℓ0 of line transversals which emanate from a fixed line ℓ₀, establish an almost tight bound of O(nk^1+ε) on the complexity of T_ℓ0, and provide a randomized algorithm which computes T_ℓ0 in comparable expected time. Slightly improved combinatorial bounds for the complexity of T_ℓ0, and comparable improvements in the cost, of constructing this set, are established for two special cases, both assuming that the polyhedra of P are pairwise disjoint: the case where ℓ₀ is disjoint from the polyhedra of P, and the case where the polyhedra of P are unbounded in a direction parallel to ℓ₀.