8 Line Transversals of Convex Polyhedra in R3∗
Haim Y. Kaplan, Natan Rubin, Micha Sharir · 2008
We establish a bound of O(n2k1+ε), for any ε>0, on the combinatorial complexity of the set T of line transversals of a collection P of k convex polyhedra in R3 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ℓ0 of line transversals which emanate from a fixed line ℓ0, establish an almost tight bound of O(nk1+ε)onthecomplexityofTℓ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 ℓ0 is disjoint from the polyhedra of P, and the case where the polyhedra of P are unbounded in a direction parallel to ℓ0. 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 R3, 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.