...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Mechatronics, IEEE/ASME Transactions on >An $bm{O(nlog n)}$ Shortest Path Algorithm Based on Delaunay Triangulation
【24h】

An $bm{O(nlog n)}$ Shortest Path Algorithm Based on Delaunay Triangulation

机译：基于Delaunay三角剖分的$ bm {O（nlog n）} $最短路径算法

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

In Euclidean and/or $lambda$-geometry planes with obstacles, the shortest path problem involves determining the shortest path between a source and a destination. There are three different approaches to solve this problem in the Euclidean plane: roadmaps, cell decomposition, and potential field. In the roadmaps approach, a visibility graph is considered to be one of the most widely used methods. In this paper, we present a novel method based on the concepts of Delaunay triangulation, an improved Dijkstra algorithm and the Fermat points to construct a reduced visibility graph that can obtain the near-shortest path in a very short amount of computational time. The length of path obtained using our algorithm is the shortest in comparison to the other fastest algorithms with $O(nlog n)$ time complexity. The proposed fast algorithm is especially suitable for those applications which require determining the shortest connectivity between points in the Euclidean plane, such as the robot arm path planning and motion planning for a vehicle.
机译：在有障碍物的欧几里得和/或λ-几何平面中，最短路径问题涉及确定源与目的地之间的最短路径。在欧几里得平面中，有三种不同的方法可以解决此问题：路线图，单元分解和势场。在路线图方法中，可见性图被认为是使用最广泛的方法之一。在本文中，我们提出了一种基于Delaunay三角剖分的概念，改进的Dijkstra算法和Fermat点的新颖方法，以构造一个减少的可见性图，该图可以在非常短的计算时间内获得最短路径。与其他具有$ O（nlog n）$时间复杂度的最快算法相比，使用我们的算法获得的路径长度最短。所提出的快速算法特别适合那些需要确定欧几里得平面上的点之间最短连接性的应用，例如机器人手臂路径规划和车辆运动规划。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号