• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>FTRA international conference on computer science and its applications;International symposium on system engineering and computer simulation;International workshop on creation, management and application of medical and biological data >The Role of Graph Theory in Solving Euclidean Shortest Path Problems in 2D and 3D
【24h】

The Role of Graph Theory in Solving Euclidean Shortest Path Problems in 2D and 3D

机译：图论在求解2D和3D欧氏最短路径问题中的作用

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Determining Euclidean shortest paths between two points in a domain is a fundamental problem in computing geometry and has many applications in GIS, robotics, computer graphics, CAD, etc. To date, solving Euclidean shortest path problems inside simple polygons has usually relied on triangulation of the entire polygons and graph theory. The question: "Can one devise a simple O(n) time algorithm for computing the shortest path between two points in a simple polygon (with n vertices), without resorting to a (complicated) linear-time triangulation algorithm?" raised by J. S.B. Mitchell in Handbook of Computational Geometry (J. Sack and J. Urrutia, eds., Elsevier Science B.V., 2000), is still open. The aim of this paper is to show that in 2D, convexity contributes to the design of an efficient algorithm for finding the approximate shortest path between two points inside a simple polygon without triangulation of the entire polygons or graph theory. Conversely, in 3D, we show that graph tools (e.g., Dijkstra's algorithm for solving shortest path problems on graphs) are crucial to find an Euclidean shortest path between two points on the surface of a convex polytope.
机译：确定域中两点之间的欧几里德最短路径是计算几何的基本问题，并且在GIS，机器人技术，计算机图形学，CAD等方面具有许多应用。迄今为止，解决简单多边形内的欧几里德最短路径问题通常依赖于三角剖分。整个多边形和图论。问题是：“有人可以设计一种简单的O（n）时间算法来计算简单多边形（具有n个顶点）中两点之间的最短路径，而不求助于（复杂的）线性时间三角剖分算法吗？”由J.S.B.提出《计算几何手册》（J. Sack和J. Urrutia编辑，Elsevier Science B.V.，2000年）中的Mitchell仍然开放。本文的目的是表明，在二维中，凸度有助于设计一种有效算法的设计，该算法可用于查找简单多边形内两点之间的近似最短路径，而无需对整个多边形或图论进行三角剖分。相反，在3D中，我们显示了图工具（例如Dijkstra解决图上最短路径问题的算法）对于找到凸多面体表面上两点之间的欧几里德最短路径至关重要。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号