[1]LI Fa-jie,KLETTE Reinhard.Shortest path algorithms for sequences of polygons[J].CAAI Transactions on Intelligent Systems,2008,3(1):23-30.
Copy

Shortest path algorithms for sequences of polygons

CAAI Transactions on Intelligent Systems[ISSN 1673-4785/CN 23-1538/TP] Volume: 3 Number of periods: 2008 1 Page number: 23-30 Column: 学术论文—人工智能基础 Public date: 2008-02-25
Title:
Shortest path algorithms for sequences of polygons
Author(s):
LI Fa-jie1;  KLETTE Reinhard2
1.Institute for Mathematics and Computing Science, University of Groningen P.O.Box 800,9700 AV Groningen，The Netherlands;
2.Computer Scienc e Department, The University of Auckland Private Bag 92019, Auckland 1142, New Ze al and
Keywords:
rubberband algorithm; shortest paths;  touring polygons;  parts cutting ;  qrectangles
CLC:
TP202+ 7
DOI:
-
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 nonco 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 L0 and L over ε, where L0 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 NPcomplete or NPhard 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 lineartime 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 ecient transformation of the generalized traveling salesman problem［J］.INFOR, 1993,31:39-44.
［8］GAREY M R，GRAHAM R L,JOHNSON D S.Some NPcomplete 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 platecutting 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 .
Similar References:

Memo

-

Last Update: 2009-05-09

Copyright © CAAI Transactions on Intelligent Systems