dc.contributor.author |
Li, Fajie |
en |
dc.contributor.author |
Klette, Reinhard |
en |
dc.date.accessioned |
2008-12-09T02:04:24Z |
en |
dc.date.available |
2008-12-09T02:04:24Z |
en |
dc.date.issued |
2007 |
en |
dc.identifier.citation |
Multimedia Imaging Report 4 (2007) |
en |
dc.identifier.issn |
1178-5789 |
en |
dc.identifier.uri |
http://hdl.handle.net/2292/3209 |
en |
dc.description |
You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the original MI_tech website http://www.mi.auckland.ac.nz/index.php?option=com_content&view=article&id=91&Itemid=76 . All other rights are reserved by the author(s). |
en |
dc.description |
In both English and Chinese |
en |
dc.description.abstract |
Given a sequence k simple polygons in a plane, and a start point p, a target point q. We approximately
compute a shortest path that starts at p, then visits each of the polygons in the specified order, and finally ends at q.
So far no solution was known if the polygons are disjoint and non-convex. By applying a rubberband algorithm, we give
an approximative algorithm with time complexity in κ(ε) · σ(n),where n is the total number of vertices of the given
polygons, and function κ(ε) is as
κ(ε)=(Lo-L)=/ε
where Lo 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 shortest path (ESP) problems
in time κ(ε)·σ(k), where k is the number of layers in a stack which contains the defined obstacles. |
en |
dc.publisher |
Computer Science Department, The University of Auckland, New Zealand |
en |
dc.relation.ispartofseries |
MI-tech Report Series |
en |
dc.rights |
Copyright CITR, The University of Auckland. You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the original CITR web site under terms that include this permission. All other rights are reserved by the author(s). |
en |
dc.rights.uri |
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm |
en |
dc.source.uri |
http://www.mi.auckland.ac.nz/tech-reports/MItech-TR-4.pdf |
en |
dc.title |
Shortest Path Algorithms for Sequences of Polygons |
en |
dc.type |
Technical Report |
en |
dc.subject.marsden |
Fields of Research::280000 Information, Computing and Communication Sciences |
en |
dc.rights.accessrights |
http://purl.org/eprint/accessRights/OpenAccess |
en |