An Improved Algorithm for Subdivision Traversal without Extra Storage
An Improved Algorithm for Subdivision Traversal without Extra Storage
复制标题
一种无需额外存储的改进细分遍历算法
DOI：
10.1007/3-540-40996-3_38
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
Pat Morin
中科院分区：
文献类型：
--
作者：
P. Bose;Pat Morin
我们描述了一种算法，用于枚举存储在任何常见的基于指针的表示中的平面细分的所有顶点、边和面，同时只使用超过存储细分所需的恒定量的内存。该算法是De Berget al(1997)提出的一种方法的改进，它将最坏情况下的运行时间从mo(N2)(Nlogn)也减少了。实验结果表明，改进后的算法不仅在最坏的情况下运行得更快，而且在许多实际情况下也是如此。
We describe an algorithm for enumerating all vertices, edges and faces of a planar subdivision stored in any of the usual pointer-based representations, while using only a constant amount of memory beyond that required to store the subdivision. The algorithm is a refinement of a method introduced by de Berget al(1997), that reduces the worst case running time fromO(n2) toO(nlogn). We also give experimental results that show that our modified algorithm runs faster not only in the worst case, but also in many realistic cases.