论文标题
Voronoi图中的最短安全路径
Shortest Secure Path in a Voronoi Diagram
论文作者
论文摘要
我们研究了计算Voronoi图中最短安全路径的问题。在这里，如果路径是一系列接触Voronoi细胞的路径，则该路径中的每个Voronoi细胞都具有固定的均匀成本。重要的是，我们允许插入新站点，在某些情况下，这会导致较短的路径。我们提出了一个$ O（n \ log n）$时间算法，用于在平面中解决此问题，该算法使用动态加权Voronoi图来计算此路径。该算法是连续和离散的Dijkstra算法的有趣组合。我们还使用CGAL实现了算法。
We investigate the problem of computing the shortest secure path in a Voronoi diagram. Here, a path is secure if it is a sequence of touching Voronoi cells, where each Voronoi cell in the path has a uniform cost of being secured. Importantly, we allow inserting new sites, which in some cases leads to significantly shorter paths. We present an $O(n \log n)$ time algorithm for solving this problem in the plane, which uses a dynamic additive weighted Voronoi diagram to compute this path. The algorithm is an interesting combination of the continuous and discrete Dijkstra algorithms. We also implemented the algorithm using CGAL.
