| 摘要 | 第1-8页 |
| Abstract | 第8-12页 |
| 目录 | 第12-15页 |
| 第一章 绪论 | 第15-23页 |
| ·计算几何及其应用 | 第15-16页 |
| ·微分几何中对测地线的研究 | 第16-17页 |
| ·离散测地问题 | 第17-19页 |
| ·本文的研究成果 | 第19-21页 |
| ·章节安排 | 第21-23页 |
| 第二章 优先队列和Dijkstra算法 | 第23-31页 |
| ·优先队列 | 第23-25页 |
| ·Dijkstra算法 | 第25-31页 |
| 第三章 离散测地问题上的已有工作及预备知识 | 第31-47页 |
| ·问题描述 | 第31页 |
| ·重要的定义和引理 | 第31-35页 |
| ·该问题的一般解决思路 | 第35-36页 |
| ·Sharir和Schorr的算法 | 第36-38页 |
| ·Mitchell等人的算法 | 第38-40页 |
| ·Chen和Han的算法 | 第40-42页 |
| ·网格曲面的展开 | 第42-44页 |
| ·算法实现 | 第44-47页 |
| 第四章 对CH算法的重大改进 | 第47-65页 |
| ·窗元过滤定理 | 第47-50页 |
| ·维护优先队列 | 第50页 |
| ·算法描述 | 第50-54页 |
| ·追踪最短路径 | 第54-56页 |
| ·实验结果 | 第56-59页 |
| ·关于ICH2算法复杂度的讨论 | 第59-60页 |
| ·单源单终点的精确最短路 | 第60-65页 |
| 第五章 两个解决单源多终点离散测地问题的近似算法 | 第65-89页 |
| ·单源多终点离散测地问题的已有近似算法 | 第65-71页 |
| ·Surazhsky等人提出的基于MMP算法的近似算法 | 第66-67页 |
| ·Fast Marching Method的主要思想及其不足之处 | 第67-71页 |
| ·由XW算法诱导出来的近似算法 | 第71-75页 |
| ·算法思想 | 第72-73页 |
| ·算法描述 | 第73-74页 |
| ·对该近似算法的评价 | 第74-75页 |
| ·基于Fast Marching Method的近似算法 | 第75-89页 |
| ·顶点接收"最短"信号的两种方式 | 第75-76页 |
| ·"最短"信号在网格边上的七种传播型态 | 第76-79页 |
| ·改进后的FMM算法 | 第79-80页 |
| ·追踪近似最短路的两种方法 | 第80-82页 |
| ·实验结果 | 第82-89页 |
| 第六章 网格曲面上两点间精确的局部最短路 | 第89-105页 |
| ·"单源单终点"离散测地问题上的代表性工作 | 第90-94页 |
| ·求解精确局部最短路的有限迭代算法 | 第94-95页 |
| ·面列的展开 | 第95-96页 |
| ·基于可视性求解限制在边序列上的精确最短路 | 第96-99页 |
| ·边序列的调整 | 第99-100页 |
| ·实验结果 | 第100-105页 |
| 第七章 有效维护动态有序集的新方法 | 第105-123页 |
| ·维持优先队列的悖论 | 第105-106页 |
| ·本文维持动态有序集的核心思想 | 第106-107页 |
| ·RBT数据结构 | 第107-111页 |
| ·动态有序集的算法实现 | 第111-121页 |
| ·求取最大元素或者最小元素 | 第111-112页 |
| ·求取次大元素或者次小元素 | 第112-113页 |
| ·查找关键字 | 第113-117页 |
| ·插入关键字 | 第117-119页 |
| ·删除关键字 | 第119-120页 |
| ·像数组一样随机访问第i个元素 | 第120-121页 |
| ·RBT应用例子 | 第121-122页 |
| ·关于复杂度的进一步探讨 | 第122-123页 |
| 第八章 结论与展望 | 第123-125页 |
| 参考文献 | 第125-143页 |
| 发表文章目录 | 第143-144页 |
| 待审文章目录 | 第144-145页 |
| 《ACM Transactions on Graphics》期刊对文[2]的审稿意见(摘录) | 第145-147页 |
| 简历 | 第147-149页 |
| 致谢 | 第149-150页 |
