Space-efficient geometric divide-and-conquer algorithms
Space-efficient geometric divide-and-conquer algorithms
复制标题
DOI：
10.1016/j.comgeo.2006.03.006
复制
发表时间：
2007-08-01
影响因子：
0.6
通讯作者：
Vahrenhold, Jan
中科院分区：
文献类型：
--
作者：
Bose, Prosenjit;Maheshwari, Anil;Vahrenhold, Jan
我们开发了一些空间效率的工具，包括一种方法来模拟分治空间效率，稳定地选择和取消选择一个子集从一个有序的集合，并计算第k个最小的元素在一个维度从一个多维集，在另一个维度排序。然后，我们应用这些工具来解决几个几何问题，有解决方案，使用某种形式的分而治之。具体来说，我们提出了一个确定性算法运行在O（n log n）的时间使用O（1）额外的内存给定的输入大小为n的最接近的对问题和随机化的解决方案运行在O（n log n）的预期时间和使用O（1）额外的空间双色最接近的对问题。对于正交线段相交问题，我们使用O（1）额外空间在O（nlog n + k）时间内解决了该问题，其中n是水平和垂直线段的数量，k是相交的数量。(C)2006 Elsevier B.V.保留所有权利。
We develop a number of space-efficient tools including an approach to simulate divide-and-conquer space-efficiently, stably selecting and unselecting a subset from a sorted set, and computing the kth smallest element in one dimension from a multidimensional set that is sorted in another dimension. We then apply these tools to solve several geometric problems that have solutions using some form of divide-and-conquer. Specifically, we present a deterministic algorithm running in O(n log n) time using O(1) extra memory given inputs of size n for the closest pair problem and a randomized solution running in O(n log n) expected time and using O(1) extra space for the bichromatic closest pair problem. For the orthogonal line segment intersection problem, we solve the problem in O(n log n + k) time using O(1) extra space where n is the number of horizontal and vertical line segments and k is the number of intersections. (C) 2006 Elsevier B.V. All rights reserved.