Name
Abstract | ||
|---|---|---|
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 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 Tl0 of line transversals which emanate from a fixed line l0, establish an almost tight bound of O(nk1+ε) on the complexity of Tl0, and provide a randomized algorithm which computes Tl0 in comparable expected time. Slightly improved combinatorial bounds for the complexity of Tl0, 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 l0 is disjoint from the polyhedra of P, and the case where the polyhedra of P are unbounded in a direction parallel to l0. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1145/1496770.1496790 | SIAM J. Comput. |
Keywords | DocType | Volume |
randomized algorithm,line transversals,fixed line l0,comparable improvement,combinatorial complexity,set tl0,collection p,construction cost,convex polyhedron,comparable expected time,combinatorial bound,convex set | Journal | 39 |
Issue | Citations | PageRank |
7 | 4 | 0.44 |
References | Authors | |
28 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Haim Kaplan | 1 | 3581 | 263.96 |
| Natan Rubin | 2 | 92 | 11.03 |
| Micha Sharir | 3 | 8405 | 1183.84 |