| 摘要 | 第3-5页 |
| ABSTRACT | 第5-6页 |
| 第一章 绪论 | 第11-17页 |
| 1.1 引言 | 第11-12页 |
| 1.2 空间受限移动对象的概念 | 第12页 |
| 1.3 空间受限移动对象概率查询的重要性 | 第12-13页 |
| 1.4 空间受限移动对象可达区域分析的意义 | 第13-14页 |
| 1.5 本文的工作 | 第14-17页 |
| 第二章 面向空间受限不确定移动对象的概率范围查询 | 第17-45页 |
| 2.1 引子 | 第17-20页 |
| 2.2 相关工作 | 第20-21页 |
| 2.3 问题定义 | 第21-23页 |
| 2.4 问题分析 | 第23-25页 |
| 2.5 我们的解决方法 | 第25-30页 |
| 2.5.1 前置逼近 | 第25-26页 |
| 2.5.2 基于标签的数据结构 | 第26-27页 |
| 2.5.3 选择真正的不确定区域 | 第27页 |
| 2.5.4 呈现的概率 | 第27-28页 |
| 2.5.5 查询处理 | 第28-30页 |
| 2.6 进一步优化 | 第30-34页 |
| 2.6.1 有效子分 | 第30-31页 |
| 2.6.2 跨度 | 第31-34页 |
| 2.7 基于预计算的方法 | 第34页 |
| 2.8 性能研究 | 第34-43页 |
| 2.8.1 实验设置 | 第34-37页 |
| 2.8.2 结果 | 第37-43页 |
| 2.9 结论 | 第43-45页 |
| 第三章 显式和隐式的约束空间概率阈值范围查询 | 第45-81页 |
| 3.1 引言 | 第45-49页 |
| 3.2 相关工作 | 第49-50页 |
| 3.3 问题定义 | 第50-54页 |
| 3.3.1 问题设置和符号 | 第50-51页 |
| 3.3.2 问题声明 | 第51-53页 |
| 3.3.3 基准方法 | 第53-54页 |
| 3.4 显式的约束空间概率阈值范围查询 | 第54-64页 |
| 3.4.1 空间修剪/验证规则 | 第54-59页 |
| 3.4.2 阈值修剪/验证规则 | 第59-62页 |
| 3.4.3 关于显式的约束空间概率阈值范围查询的查询 | 第62-64页 |
| 3.5 隐式的约束空间概率阈值范围查询 | 第64-68页 |
| 3.5.1 增强的多步计算 | 第64-68页 |
| 3.5.2 关于隐式约束空间概率阈值范围查询的查询处理 | 第68页 |
| 3.6 进一步优化 | 第68-70页 |
| 3.7 实验评估 | 第70-78页 |
| 3.7.1 实验设置 | 第70-72页 |
| 3.7.2 性能研究 | 第72-78页 |
| 3.8 结束语 | 第78页 |
| 附录 | 第78-81页 |
| 第四章 计算移动对象可达区域 | 第81-105页 |
| 4.1 引言 | 第81-85页 |
| 4.2 预备知识 | 第85-88页 |
| 4.2.1 问题定义和符号 | 第85-87页 |
| 4.2.2 关于“大致解”的分析 | 第87-88页 |
| 4.3 一个O(n~3) 算法 | 第88-94页 |
| 4.3.1 归约 | 第88页 |
| 4.3.2 计算环可视区域 | 第88-93页 |
| 4.3.3 算法 | 第93-94页 |
| 4.4 一个O(n~2 log n)算法 | 第94-97页 |
| 4.4.1 最短路径图预备知识 | 第94-95页 |
| 4.4.2 构造线段障碍物情形下的SP M (s′) | 第95-96页 |
| 4.4.3 算法 | 第96-97页 |
| 4.5 一个O(nlog n) 算法 | 第97-101页 |
| 4.5.1 最短路径图SP M (s)的区域 | 第97-99页 |
| 4.5.2 算法 | 第99-101页 |
| 4.6 结束语 | 第101页 |
| 附录 | 第101-105页 |
| 第五章 计算圆弧多边形布尔操作 | 第105-129页 |
| 5.1 引言 | 第105-106页 |
| 5.2 相关工作 | 第106-108页 |
| 5.2.1 传统多边形的布尔操作 | 第107页 |
| 5.2.2 二次曲线/通用（conic/general）多边形的布尔操作 | 第107-108页 |
| 5.3 预备知识 | 第108-110页 |
| 5.3.1 基本概念 | 第108-109页 |
| 5.3.2 表示 | 第109页 |
| 5.3.3 算法的上层 | 第109-110页 |
| 5.4 算法RE2L的核心 | 第110-115页 |
| 5.4.1 相关边 | 第110-111页 |
| 5.4.2 两个顺序列表 | 第111-112页 |
| 5.4.3 两个标签 | 第112-114页 |
| 5.4.4 算法 | 第114-115页 |
| 5.5 两个新的链表 | 第115-118页 |
| 5.5.1 新的附加点 | 第115-116页 |
| 5.5.2 分解弧 | 第116页 |
| 5.5.3 算法 | 第116-118页 |
| 5.6 遍历 | 第118-121页 |
| 5.6.1 入-出属性 | 第118页 |
| 5.6.2 遍历规则 | 第118-120页 |
| 5.6.3 算法 | 第120-121页 |
| 5.7 时/空复杂度 | 第121-122页 |
| 5.8 性能评估 | 第122-127页 |
| 5.8.1 方法 | 第122-123页 |
| 5.8.2 实验设置 | 第123-124页 |
| 5.8.3 实验结果 | 第124-127页 |
| 5.9 扩展 | 第127页 |
| 5.10 结论 | 第127-129页 |
| 全文总结 | 第129-133页 |
| 参考文献 | 第133-145页 |
| 致谢 | 第145-147页 |
| 攻读学位论文期间发表的学术论文目录 | 第147-149页 |
