[1]李发捷,KLETTE Reinhard.多边形序列的最短路径算法[J].智能系统学报,2008,3(1):23-30.
LI Fa-jie,KLETTE Reinhard.Shortest path algorithms for sequences of polygons[J].CAAI Transactions on Intelligent Systems,2008,3(1):23-30.
点击复制
LI Fa-jie,KLETTE Reinhard.Shortest path algorithms for sequences of polygons[J].CAAI Transactions on Intelligent Systems,2008,3(1):23-30.
多边形序列的最短路径算法
《智能系统学报》[ISSN 1673-4785/CN 23-1538/TP] 卷:
3
期数:
2008年第1期
页码:
23-30
栏目:
学术论文—人工智能基础
出版日期:
2008-02-25
- Title:
- Shortest path algorithms for sequences of polygons
- 文章编号:
- 1673-4785(2008)01-0023-08
- Keywords:
- rubberband algorithm; shortest paths; touring polygons; parts cutting ; qrectangles
- 分类号:
- TP202+ 7
- 文献标志码:
- A
- 摘要:
- 给定平面上一个含k个简单多边形的序列及一个起点p和一个终点q，近似地计算一条最短路径使得它开始于p点，然后按指定的次序访问每个多边形，最后终止于q点. 如果多边形是两两不相交且是非凸的，那么此问题至今还没有算法解.应用一种R算法，给出复杂性为κ(ε)?O(n)的一种近似算法，这里n是给定多边形的顶点总数，函数κ( ε)定义为L0与L的差与ε的商，其中L0是初始路径长度，L是最优路径长度，ε是计算精确度.给定的R算法稍作修改也能用来近似地解决3个NP完全或NP困难的三维欧几里德最短路径问题(ESP).它们的复杂性均为κ(ε)?O(k)，这里k是含有所给定的障碍物的堆的层数.
- Abstract:
- Given a sequence of k simple polygons in a plane, and a start po int p, a target point q. We approximately compute a shortest path that s tarts at p, then visit each of the polygons in the specified order, and fina lly end at q. So f ar no solution is known if the polygons are disjoint with each other and nonco nvex. By applying a rubberband algorithm, we give an approximate algorithm with time complexity in κ(ε)?O(n), where n is the total number of vert ices of the given polygons, and function κ(ε) is the difference between L0 and L over ε, where L0 is the length of the initial path, and L is the true (i.e., optimum) path length. The given rubberband algorithm can also be applied to solve approximately three NPcomplete or NPhard 3D Euclidean s hortest path (ESP) problems in κ(ε)?O(k), where k is the number of l ayers in a stack which contains the defined obstacles.
- 参考文献/References:
-
［1］ BULOW T,KLETTE R.Digital curves in 3D space and a lineartime length estimation algorithm［J］.IEEE Trans Pattern Analysis Machine Intelligence, 2002,24(7):962 -970.
［2］LI F,KLETTE R.Exact and approximate algorithms for the calculation of short est paths［R］.IMA Minneapolis 2006.www.ima.umn.edu/preprints/oct2006.
［3］DROR M，EFRAT A，LUBIW A，et al.Touring a sequence of polygons［C］// Proc STOC.San Diego,USA,2003.
［4］HOEFT J，PALEHAR U S.Heuristics for the platecutting traveling salesman pro blem［J］.IIE Transactions, 1997,29(9):719-731.
［5］LAWLER E，LENSTRA J，RINNOOY K A，et al.The traveling salesman problem［M］ .New York:John Wiley and Sons, 1985 .
［6］LAPORTE G，MERCURE H，NOBERT Y.Generalized traveling salesman problem throu gh n clusters［J］.Discrete Applied Mathematics, 1987,18(2):185-197.
［7］NOON C E，BEAN J C.An ecient transformation of the generalized traveling salesman problem［J］.INFOR, 1993,31:39-44.
［8］GAREY M R，GRAHAM R L,JOHNSON D S.Some NPcomplete geometric problems［C］ // Proc ACM Sympos Theory Computing.Hershey,USA,1976.
［9］GEOFFRION A M.Lagrangean relaxation and its uses in integer programming［J ］.Mathematical Programming Study,1974(2):28-114.
［10］GUIGNARD M，KIM S.Lagrangean decomposition:amodel yielding s tronger Lagran gean bounds［J］.Mathematical Programming, 1987,31(3):271-274.
［11］DROR M.Polygon platecutting with a given order［J］.IIE Transact ions, 19 99,31(3):271-274
［12］MITCHELL J S B，SHARIR M.New results on shortest paths in th ree dimensions ［C］// Proc SCG Brooklyn.New York,2004.
［13］CANNY J，REIF J H.New lower bound techniques for robot motion planning pro blems［C］// Proc IEEE Conf Foundations Computer Science.Los Angeles,USA,1987 .
- 相似文献/References:
-
[1]郇战,陈学杰,梁久祯.手机惯导与RFID的盲人导航系统设计与实现[J].智能系统学报,2019,14(3):491.[doi:10.11992/tis.201804058]
HUAN Zhan,CHEN Xuejie,LIANG Jiuzhen.Design and implementation of blind-navigation system based on RFID and smartphones’ inertial navigation[J].CAAI Transactions on Intelligent Systems,2019,14():491.[doi:10.11992/tis.201804058]
备注/Memo
收稿日期：2007-06-16.
作者简介：
李发捷，男，1965年生，博士，荷兰格罗宁根大学博士后，主要研究方向为数字几何、计算几何、天文数据的计算机视觉分析，发表论文10余篇.
KLETTE Reinhard，男，1950年生，博士，教授，主要研究方向为并行计算、图像处理、计算机视觉、数字几何、计算几何，发表论文250多篇，出版专著8部，编辑专著21部. KLETTE Reinhard 教授担任“IEEE Trans.PAMI”(Associate Editor),“CAAI Transactions on Intelligent Systems(智能系统学报)”(Member of E ditorial Board)，“Springers Computational Imaging and Vision”(Editor)，“Inter n ational Journal of Computer Vision” (Member of Editorial Board)，“Machine GRAP HICS &VISION”(Member of Advisory Board)，“OptoElectronics Review”(Member of E ditorial Advisory Board)等期刊的编辑或委员.是以下国际学术会议的主要发起人：CAIP conferen ces(International Conference on C omputer Analysis of Images and Patterns)(Member of Steering Committee).是28场国际学术会议(在智利、德国、新西兰、台湾等地)的主席或副主席.是2005年DAG 〖JP2〗M奖获得者之一.曾应邀在阿根廷、中国、印度、意大利、新西兰、台湾和美国等地国际学术会议作报告.在德国柏林技术大学、德国哥廷根大学和新西兰奥克兰大学已指导培养14名博士和100多名硕士.
通讯作者：李发捷.E-mail:F.li@rug.nl.
更新日期/Last Update:
2009-05-09