נתן רובין

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 we 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ℓ₀ 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 ℓ₀. Our result is related to the problem of bounding the number of geometric permutations of a collection C of k pairwise-disjoint convex sets in ℝ³, namely, the number of distinct orders in which the line transversals of C visit its members. We obtain a new partial result on this problem.