We present a new algorithm for finding minimum-link rectilinear paths among h rectilinear obstacles with a total of n vertices in the plane. After the plane is triangulated, for any point s, our algorithm builds an O(n)-size data structure in O(n+h log h) time, such that given any query point t, we can compute a minimum-link rectilinear path from s to t in O(log n + k) time, where k is the number of edges of the path, and the query time is O(log n) if we only want to know the value k. The previously best algorithm solves the problem in O(n log n) time.
展开▼
机译：我们提出了一种用于在平面中总共N个顶点的H直线障碍物中找到最小链路直线路径的新算法。在平面三角形后，对于任何点，我们的算法在O（n + h log h）时间内构建了一个（n）的数据结构，使得给定任何查询点t，我们可以计算最小链路直线从o（log n + k）时间的路径，其中k是路径的边缘数，如果我们只想知道值k，则查询时间是o（log n）。先前最好的算法解决了O（n log n）时间的问题。
展开▼
