离散测地问题是指限制于网格曲面上的最短路径问题.它最早出现于地理导航系统和机器人的运动路线控制等应用领域,并已经成为计算几何中一个经典的教科书问题.寻求解决该问题的高效算法不仅是数字几何处理的重要任务,也是计算机图形学发展的必然需求.就源点和终点的数目而论,离散测地问题有三个版本:单源单终点、单源多终点和多源多终点.其中,单源多终点的离散测地问题尤为重要,它是解决其余两个问题的基础.Sharir和Schorr于1986年根据Dijkstra算法的思想提出了一个仅适用于凸多面体的O(n~3 log n)算法,其中n为面数.尽管如此,这是针对该问题的首个有效算法.次年,Mitchell等人(MMP)用窗元来记录具有共同边序列的一组最短路信息,并把Dijkstra算法的精神发挥到极致,给出了一个O(n~2 log n)时间和O(n~2)空间的算法.他们的算法适用于一般的网格曲面.1990年,Chen和Han(CH)观察到可以为每条有向边保存一个关键窗元,以阻止无用窗元的派生.于是他们另辟蹊径,逐层建立起一棵大小为O(n~2)的窗元树,并证明了离散测地问题可以在O(n~2)时间和O(n)空间内解决.有意思的是,Surazhsky等人在2005年的SIGGRAPH会议上宣布O(n~2 log n)时间的MMP算法远比O(n~2)时间的CH算法要快.为了揭示其中的原因,我们对离散测地问题做了深入研究.研究结果表明,尽管CH算法在理论时间复杂度上占优,但它生成的窗元树过于庞大—在很多的例子中,超过99%的结点都是无用的.于是我们用两个技巧对CH算法加以改造:其一,提出了一个简单有效的窗元过滤定理,用顶点处的距离估计值过滤掉大部分无用的窗元;其二,像Dijkstra算法那样维护一个优先队列,从而按照由近及远的方式派生离散事件.大量的实验结果表明,改进后的CH算法(简称XW算法)比原来的CH算法在性能方面提高千倍以上.与MMP算法相比,我们的算法不仅速度更快,而且占用的空间仅为其百分之一.所以我们有理由相信,XW算法是当今针对该问题的首选算法.尽管如此,我们必须指出,维护优先队列使XW算法的理论时间复杂度变成O(n~2 log n).为了使研究工作更加深入,我们制订了两个研究方向:一个是寻求解决离散测地问题的其它算法,另一个是解释这个悖论:为什么使用优先队列之后,XW算法的实际效率提高了,而它的时间复杂度却变坏了.在第一个研究方向上,我们做了以下几项工作:(1)基于惠更斯的波动原理,我们把“最短”信号在网格表面上的传播分作七种具体形式,从而成功地改造了著名的Fast Marching Method(FMM),得到了一个更好的求解单源多终点离散测地问题的近似算法.(2)对于指定的∈,我们可以在XW算法中使用以∈为参数的过严格的窗元过滤定理,从而诱导出一个精度可调的近似算法.当∈=0时,该近似算法恰好就是XW算法;当∈→∞时,它退化为Dijkstra算法.(3)受费马的光路最路原理的启发,我们提出了一个基于可视性求解边序列上精确最短路的高效算法.在此基础上,我们可以通过有限次的迭代把近似的初始路径收敛到精确的局部最短路径;在初始路径足够短的情况下,我们求出的路径也是精确的全局最短路.(4)从CH算法或者XW算法中我们诱导出一个精确求解单源单终点的离散测地问题的A~*算法.至于第二个研究方向,我们仔细分析了使用优先队列的经典算法,发现了相似的悖论.以Dijkstra算法为例,如果我们避免维护优先队列、代之以层次派生,则在图接近于树形结构或者各边权值非常接近的情况下,算法将由O(m+n log n)变为O(m),其中m为图中的有向边的数目,n为图中顶点的数目.这意味着此时维护优先队列是一种负担!这有悖于我们通常的认识—维护优先队列是一个普遍适应的算法优化技巧.所以我们猜测,维护优先队列只是一个常数时间的行为,并不会增加相关算法的复杂度.为了求证这个猜测,我们思考了一个更大的问题,就是如何有效地维持关键字为位串的动态有序集,以支持以下五种操作:求取最大(小)关键字,求取次大(小)关键字,查找给定的关键字,插入一个关键字和删除指定的关键字.可喜的是,我们确实找到了一种巧妙的数据结构,不妨称之为RBT(Rich Binary Tree),它同时具备二叉搜索树和数字查找树的性质;并且,所有结点都保存了它与祖先结点中次人者和次小者的最高差别位.更进一步,我们提出了一套基于RBT的算法,它们可以在O(L)时间内完成中这五种操作中的任意一个,从而维持了一个O(L)时间的动态有序集,其中L为关键字的长度.所以,RBT支持O(L)时间的查找,O(nL)时间的排序,以及O(L)时间的优先队列.在L为常量的情况下,我们可以认为维持优先队列确实不会增加相关算法的复杂度.这在一定程度上诠释了上面提出的悖论.事实上,RBT可被视为一种通用的数据结构,它能够高效解决大多数与“序”有关的问题,比如查找、排序和维持优先队列等等.以长关键字的排序为例,基于RBT的排序方法在时间上大致线性增长,而且支持O(L)时间的动态插入和动态删除.实验结果表明,该排序方法优于O(n log n)时间的快速排序.鉴于XW算法在时间与空间上分别优于CH算法与MMP算法千倍及百倍,这一根本性改革有望引发出离散测地问题的一系列后继理论研究及相关应用研究,把离散测地问题的研究推向一个新的高潮;而鉴于离散测地问题的地位及作用,毫无疑问,XW算法有望对离散微分几何的研究方法及理论思想产生深远的影响.因为该算法速度快、空间少,并且求出来的最短路径是全局的、精确的,所以它将会在数字几何处理和计算机图形学中得到广泛的应用.比如说,基于相似性的曲面建模、曲面参数化、网格曲面的分块、曲面上的距离量度和重新网格化等问题都可以借助最短路径找到好的解决方案.在动态有序集的研究上,我们提出的RBT数据结构巧妙新颖、性质良好,在计算机学科中首次出现.RBT结构以及基于RBT的算法必将极大地提高信息处理的能力与效率,积极地推动算法理论的完善与进步,具有明显的理论意义和应用价值.