2008/07/08 by Haim Kaplan, Kaplan, Haim, Natan Rubin +3
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #cs.CG
paper · pdf · doi:10.48550/arxiv.0807.1221
10 pages+ 15 page appendix
arxiv created 2008/07/08 · openalex publication_date 2008/07/08 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We establish a bound of O(n2k1+\eps), for any \eps>0, on the combinatorial complexity of the set \T of line transversals of a collection ¶ of k convex polyhedra in \reals3 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 \TL of line transversals which emanate from a fixed line ℓ0, establish an almost tight bound of O(nk1+\eps) on the complexity of \TL, and provide a randomized algorithm which computes \TL in comparable expected time. Slightly improved combinatorial bounds for the complexity of \TL, 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.