Constant-Work-Space Algorithms for Geometric Problems
Constant-Work-Space Algorithms for Geometric Problems
复制标题
DOI：
10.20382/jocg.v2i1a4
复制
发表时间：
2010-10
期刊：
影响因子：
--
通讯作者：
T. Asano;Wolfgang Mulzer;G. Rote;Yajun Wang
中科院分区：
文献类型：
--
作者：
T. Asano;Wolfgang Mulzer;G. Rote;Yajun Wang
恒定工作空间算法可以仅使用除了其输入之外的恒定的许多存储单元，其被提供为只读阵列。我们展示了如何在恒定工作空间模型中巧妙地构造几种几何结构。传统算法将输入处理为合适的数据结构（例如双连接边列表），该结构允许对手头的结构进行精确遍历。然而，在恒定工作空间设置中，我们不能命令这样做。相反，我们提供了通过访问输入来计算y上所需特征的操作，没有额外的空间。利用这些运算枚举所有的特征，就可以得到整个几何结构.当然，我们必须以较慢的运行时间来为节省的空间付出代价。虽然标准数据结构允许我们在恒定时间内实现遍历操作，但我们的方案通常需要线性时间来读取每一步的输入数据。我们开始与两个简单的问题：三角化一个平面点集和nding一个简单的多边形的梯形分解。在这两种情况下，相邻的特征可以在每一步的线性时间内枚举，从而产生输出整个结构的总二次运行时间。实际上，我们表明，以前的结果结转到Delaunay三角剖分，因此Voronoi图。这也意味着我们可以在二次时间和恒定工作空间中计算平面点集的最大空圆。作为另一个应用，我们演示了如何枚举的功能的欧氏最小生成树（埃姆斯特）在每一步的二次时间，使整个埃姆斯特可以找到立方时间使用恒定的工作空间。
Constant-work-space algorithms may use only constantly many cells of storage in addition to their input, which is provided as a read-only array. We show how to construct several geometric structures eciently in the constant-work-space model. Traditional algo- rithms process the input into a suitable data structure (like a doubly-connected edge list) that allows ecient traversal of the structure at hand. In the constant-work-space setting, however, we cannot aord to do this. Instead, we provide operations that compute the desired features on the y by accessing the input with no extra space. The whole geomet- ric structure can be obtained by using these operations to enumerate all the features. Of course, we must pay for the space savings by slower running times. While the standard data structure allows us to implement traversal operations in constant time, our schemes typically take linear time to read the input data in each step. We begin with two simple problems: triangulating a planar point set and nding the trapezoidal decomposition of a simple polygon. In both cases adjacent features can be enumerated in linear time per step, resulting in total quadratic running time to output the whole structure. Actually, we show that the former result carries over to the Delaunay triangulation, and hence the Voronoi diagram. This also means that we can compute the largest empty circle of a planar point set in quadratic time and constant work-space. As another application, we demonstrate how to enumerate the features of an Euclidean minimum spanning tree (EMST) in quadratic time per step, so that the whole EMST can be found in cubic time using constant work-space.