Line Transversals of Convex Polyhedra in R3
Line Transversals of Convex Polyhedra in R3
复制标题
R3 中凸多面体的线横截面
DOI：
10.1137/080744694
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
M. Sharir
中科院分区：
文献类型：
--
作者：
Haim Kaplan;Natan Rubin;M. Sharir
对于任意e > 0，我们建立了R3中k个凸多面体的集合P的线截集T的组合复杂性的O（n2k1+e）的界，并给出了一个在相当的预期时间内计算T的边界的随机算法.因此，当k L n时，T的复杂度（和构造成本）的新边界改进了先前最好的已知边界，其在n中几乎是立方的。
为了得到上述结果，我们研究了从固定直线l0发出的直线横截集Tl0，建立了Tl0复杂性的O（nk 1 +e）的几乎紧界，并提供了一个在可比的预期时间内计算Tl0的随机算法。稍微改进的组合界限的复杂性Tl0，和可比的改进，构建这一组的成本，建立了两种特殊情况下，都假设P的多面体是成对不相交的：的情况下，L0是不相交的多面体的P，和的情况下，P的多面体是无界的方向平行于L0。
We establish a bound of O(n2k1+e), for any e > 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 L 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+e) 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.