从离散测地问题到动态有序集

《从离散测地问题到动态有序集》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、浙江大学理学院博士学位论文从离散测地问题到动态有序集姓名：辛士庆申请学位级别：博士专业：应用数学指导教师：王国瑾20080415摘要离散测地问题是指限制于网格曲面上的最短路径问题．它最早出现于地理导航系统和机器人的运动路线控制等应用领域，并已经成为计算几何中一个经典的教科书问题．寻求解决该问题的高效算法不仅是数字几何处理的重要任务，也是计算机图形学发展的必然需求．就源点和终点的数日而论，离散测地问题有三个版本：单源单终点、单源多终点和多源多终点．其中，单源多终点的离散测地问题尤为重要，它是解决其余两个问题的基础．Sharir和Schorr于1986年根据Dijkstra算法

2、的思想提出了一个仪适用于凸多面体的O(nalogn)算法，其中n为面数．尽管如此，这足针对该问题的首个有效算法．次年，Mitchell等人(MMP)用窗元来记录具有共同边序列的一组最短路信息，并把Dijkstra算法的精神发挥到极致，给出了一个O(n2logn)时间和O(n2)空间的算法．他们的算法适用于一般的网格曲面．1990年，Chen和Han(CH)观察到可以为每条有向边保存一个关键窗元，以阻止无用窗元的派生．于是他们另辟蹊径，逐层建立起一棵大小为O(n2)的窗元树，并证明了离散测地问题可以在O(n2)时间和o(n)空间内解决．有意思的是，Surazhsky等人在20

3、05年的SIGGRAPH会议上宣布O(n2logn)时间的MMP算法远比o(n2)时间的CH算法要快．为了揭示其中的原因，我们对离散测地问题做了深入研究．研究结果表明，尽管CH算法在理论时问复杂度上占优，但它生成的窗元树过于庞大一在很多的例子中，超过99％的结点都是无用的．于是我们用两个技巧对CH算法加以改造：其一，提出了一个简单有效的窗元过滤定理，用顶点处的距离估计值过滤掉大部分无用的窗元；其二，像Dijkstra算．法那样维护一个优先队列，从而按照由近及远的方式派生离散事件．大量的实验结果表明，改进后的CH算法(简称XW算法)比原来的CH算法在性能方面提高千倍以上．与M

4、MP算法相比，我们的算法不仅速度更快，而且占用的空间仅为其百分之一．所以我们有理由相信，XW算法是当今针对该问题的首选算法．尽管如此，我们必须指出，维护优先队列使XW算法的理论时间复杂度变成D(n2logn)．为了使研究工作更加深入，我们制订了两个研究方向：一个是寻求解决离散测地问题的其它算法，另一个足解释这个悖论：为什么使用优先队列之后，XW算法的实际效率提高了，而它的时从离散测地问题到动态有序集间复杂度却变坏了．在第一个研究方向上，我们做了以下几项工作：(1)基于惠更斯的波动原理，我们把“最短”信号在网格农面上的传播分作七种具体形式，从而成功地改造了著名的FastMar

5、chingMethod(FMM)，得到了一个更好的求解单源多终点离散测地问题的近似算法．(2)对jj：指定的￡，我们可以在XW算法中使用以E为参数的过严格的窗元过滤定理，从而诱导出一个精度可调的近似算法．当E=0时，该近似算法恰好就是XW算法；当E_oo时，它退化为Dijkstrw,算法．(3)受费马的光路最路原理的肩发，我们提出了一个基于可视性求解边序列上精确最短路的高效算法．在此基础，卜，我们可以通过有限次的迭代把近似的初始路径收敛到精确的局部最短路径；在初始路径足够短的情况下，我们求出的路径也是精确的全局最短路．(4)从CH算法或哲XW算法中我们诱导出。。个精确求解单

6、源单终点的离散测地问题的”算法．至于第二个研究方向，我们仔细分析了使用优先队列的经典算法，发现了相似的悖论．以Dijkstra算法为例，如果我们避免维护优先队列、代之以层次派生，则在图接近于树形结构或者各边权值非常接近的情况下，算法将由O(m+nlogn)变为0(m)，其中m为图中的有向边的数目，n为图巾顶点的数月．这意味着此时维护优先队列是一种负担!这有悖于我们通常的认识一维护优先队列是一个普遍适应的算法优化技巧．所以我们猜测，维护优先队列只是一个常数时间的行为，并不会增加相关算法的复杂度．为了求证这个猜测，我们思考了一个更大的问题，就是如何有效地维持关键字为位串的动念有

7、序集，以支持以下五种操作：求取最大(小)关键字，求取次大(小)关键字，查找给定的关键宁，插入一个关键字和删除指定的关键字．可喜的是，我们确实找到了一种巧妙的数据结构，不妨称之为RBT(RichBinary仉e)，它同时具备二叉搜索树和数字查找树的性质；并且，所有结点都保存了它与祖先结点巾次人者和次小者的最高差别位．更进一步，我ffJ提出了一套基于RBT的算法，它们可以在O(L)时间内完成中这五种操作中的任意一个，从而维持了一个O(L)时『开J的动态有序集，其中工为关键字的长度．所以，RBT支持O(L)时间的查找，O