The complexity of many cells in arrangements of planes and related problems
The complexity of many cells in arrangements of planes and related problems
复制标题
多单元平面排列的复杂性及相关问题
DOI：
--
复制
发表时间：
2015
影响因子：
0.8
通讯作者：
M. Sharir
中科院分区：
文献类型：
--
作者：
H. Edelsbrunner;L. Guibas;M. Sharir
我们考虑了三维空间中涉及点和面的几个问题。我们的主要结果是：(I)在n个平面ISO(m2/3nlogn+n2)的排列中，不同单元的最大面数；在最坏情况下，我们可以计算每个平面中的一个点所指定的单元的面数(m2/3nlog3n+n2logn)。(Ii)平面与其排列的m个顶点之间的最大入射次数Io(m2/3nlogn+n2)，但对于任何−δ>；0，对于任何三个不共线的点的集合，这个数目仅为O(m/5δn4/5+2δ+m+nlogm)。(Iii)对于任意的点集合，我们可以用一个随机算法来计算它们与n个平面之间的关联次数，该算法的预期时间复杂度为(m~3/4−δn3/4+3δ+m)log2n+n logn logm)，对于任意δ>；0。(Iv)Givenm点和n平面，对于任意−δ>；0，我们可以在随机期望时间o([m~3/4δn3/4+3δ+m]log2n+n logn logm)中找到紧接在每个点下方的平面。(V)在n个超平面ind维的排列中，限定不同单元的最大面数(即(d−1)维面)，d>；3，iso(m2/3d/3logn+nd−1)。这也是超平面的维度与其排列的m个顶点之间的关联次数的上界。(I)和(V)中的组合界和(Ii)中的一般界几乎是紧的。
We consider several problems involving points and planes in three dimensions. Our main results are: (i) The maximum number of faces boundingm distinct cells in an arrangement ofn planes isO(m2/3n logn +n2); we can calculatem such cells specified by a point in each, in worst-case timeO(m2/3n log3n+n2 logn). (ii) The maximum number of incidences betweenn planes andm vertices of their arrangement isO(m2/3n logn+n2), but this number is onlyO(m3/5−δn4/5+2δ+m+n logm), for anyδ>0, for any collection of points no three of which are collinear. (iii) For an arbitrary collection ofm points, we can calculate the number of incidences between them andn planes by a randomized algorithm whose expected time complexity isO((m3/4−δn3/4+3δ+m) log2n+n logn logm) for anyδ>0. (iv) Givenm points andn planes, we can find the plane lying immediately below each point in randomized expected timeO([m3/4−δn3/4+3δ+m] log2n+n logn logm) for anyδ>0. (v) The maximum number of facets (i.e., (d−1)-dimensional faces) boundingm distinct cells in an arrangement ofn hyperplanes ind dimensions,d>3, isO(m2/3nd/3 logn+nd−1). This is also an upper bound for the number of incidences betweenn hyperplanes ind dimensions andm vertices of their arrangement. The combinatorial bounds in (i) and (v) and the general bound in (ii) are almost tight.