On Geometric Path Query Problems
On Geometric Path Query Problems
复制标题
关于几何路径查询问题
DOI：
--
复制
发表时间：
1997
影响因子：
--
通讯作者：
K. Klenk
中科院分区：
文献类型：
--
作者：
D. Chen;O. Daescu;K. Klenk
本文研究了几种几何路径查询问题。我们的重点主要是在所谓的“两点”查询问题：给定一个场景的不相交的多边形障碍物与总共n个顶点在平面上，我们构建有效的数据结构，使快速报告的“最佳”避障路径（或其长度，成本，方向等）。在以在线方式给出的两个任意查询点s和t之间。我们考虑几个最优性准则下的几何路径：
m Lsb{p}$长度，边数（称为链接），相对于某个方向的单调性，以及长度和链接的某些组合。我们的方法是围绕网关的概念，在平面上控制我们寻求的路径的少量容易识别的点。我们提出了解决方案的一般情况下，基于查询点的最小尺寸的可见性多边形的计算。我们也给出了更好的解决方案，几个特殊情况下，新的几何观测的基础上。很少有算法是以前已知的两点查询问题，我们的研究结果代表了一个显着的除了该领域。除了我们的理论结果，我们还进行实验研究的几何算法的实施所涉及的问题。这些研究是实施全面路径规划系统的必要的第一步。
In this dissertation, we study several geometric path query problems. Our focus is primarily on the so-called "two-point" query problem: Given a scene of disjoint polygonal obstacles with totally n vertices in the plane, we construct efficient data structures that enable fast reporting of an "optimal" obstacle-avoiding path (or its length, cost, directions, etc.) between two arbitrary query points s and t that are given in an on-line fashion. We consider geometric paths under several optimality criteria: $
m Lsb{p}$ length, number of edges (called links), monotonicity with respect to a certain direction, and some combinations of length and links. Our methods are centered around the notion of gateways, a small number of easily identified points in the plane that control the paths we seek. We present solutions for the general cases based upon the computation of the minimum size visibility polygon for query points. We also give better solutions for several special cases based upon new geometric observations. Very few algorithms were previously known for two-point query problems and our results represent a significant addition to the field. In addition to our theoretical results, we also perform experimental studies on issues involved with the implementation of geometric algorithms. These studies are a necessary first step in the implementation of full path-planning systems.