Two-point Euclidean shortest path queries in the plane
Two-point Euclidean shortest path queries in the plane
复制标题
平面内两点欧氏最短路径查询
DOI：
--
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
Joseph S. B. Mitchell
中科院分区：
文献类型：
--
作者：
Yi;Joseph S. B. Mitchell
我们考虑基本几何最短路径问题的两点查询版本：给定一组多边形障碍物，iu iu iu，总共具有n个顶点，构建一个数据结构，使得对于任何两个查询点S和T，我们都可以有效地确定欧几里得最短的避免障碍物的长度（s，t）， *（s，t）从s到t。 ），与其（组合）大小成正比。我们提出了解决此两点查询问题的各种方法log'n）或最佳O（log n）查询时间，使用多项式空间数据结构，在空间和查询时间之间进行了各种权衡，而几个结果却大约是欧几里得的最短路径查询公开的问题以获取问题的确切版本的sublinear查询时间。
We consider the two-point query version of the fundamental geometric shortest path problem: Given a set h of polygonal obstacles iu the plane, having a total of n vertices, build a data structure such that for any two query points s and t we can efficiently determine the length, d(s,t), of an Euclidean shortest obstacle-avoiding path, *(s,t), from s to t. Additionally, our data structure should allow one to report the path x(s, t), in time proportional to its (combinatorial) size. We present various methods for solving this two-point query problem, including algorithms with o(n), O(log n+h), 0( h log n), O(log’ n) or optimal O(log n) query times, using polynomial-space data structures, with various tradeoffs between space and query time. While severa results have been known for approtimate twepoint Euclidean shortest path queries, it has been a well-publicized open problem to obtain sublinear query time for the exact version of the problem. Our methods also yield data structures for twc+point shortest path queries on nonconvex polyhedral