Separators for sphere-packings and nearest neighbor graphs
Separators for sphere-packings and nearest neighbor graphs
复制标题
DOI：
10.1145/256292.256294
复制
发表时间：
1997-01-01
影响因子：
2.5
通讯作者：
Vavasis, SA
中科院分区：
文献类型：
--
作者：
Miller, GL;Teng, SH;Vavasis, SA
d维中n个球的集合形成一个k层系统，如果空间中没有一点被超过k个球覆盖。我们证明了对于每个k层系统Gamma，存在一个球面S，它与Gamma的至多O（k（1/d）n（1-1/d））个球相交，并将Gamma的其余部分分成两部分：分别在球面S内部和外部的部分，使得较大的部分至多包含（1-1/（d+2））n个球.这是一个复杂度为O（k（1/d）n（1-1/d））的算法。我们还提出了一个简单的随机算法来找到这样一个球在O（n）的时间。我们的结果意味着每个d维n点的k-最近邻图都有一个长度为O（k（1/d）n（1-1/d））的分隔符。结合Koebe的一个结果，即每个三角化平面图都同构于一个圆盘填充的交图，我们的结果不仅给出了Lipton和Tarjan的平面分离定理的一个新的几何证明，而且将其推广到高维空间.分离器算法可用于固定维空间中的点定位和几何分治。
A collection of n balls in d dimensions forms a k-ply system if no point in the space is covered by more than k balls. We show that for every k-ply system Gamma, there is a sphere S that intersects at most O(k(1/d)n(1-1/d)) balls of Gamma and divides the remainder of Gamma into two parts: those in the interior and those in the exterior of the sphere S, respectively, so that the larger part contains at most (1-1/(d+2))n balls. This bound of O(k(1/d)n(1-1/d)) is the best possible in both n and k. We also present a simple randomized algorithm to find such a sphere in O(n) time. Our result implies that every k-nearest neighbor graph's of n points in d dimensions has a separator of size O (k(1/d)n(1-1/d)). In conjunction with a result of Koebe that every triangulated planar graph is isomorphic to the intersection graph of a disk-packing, our result not only gives a new geometric proof of the planar separator theorem of Lipton and Tarjan, but also generalizes it to higher dimensions. The separator algorithm can be used for point location and geometric divide and conquer in a fixed dimensional space.