SHORTEST PATH QUERIES AMONG WEIGHTED OBSTACLES IN THE RECTILINEAR PLANE.
Saved in:
| Title: | SHORTEST PATH QUERIES AMONG WEIGHTED OBSTACLES IN THE RECTILINEAR PLANE. |
|---|---|
| Authors: | Chen, Danny Z.1 dchen@cse.nd.edu, Klenk, Kevin S.1 kklenk@cse.nd.edu, Tu, Hung-Yi T.2 hytu@simon.pu.edu.tw |
| Source: | SIAM Journal on Computing. 2000, Vol. 29 Issue 4, p1223. 24p. |
| Subjects: | Data structures, COMSKEE (Computer program language), Computer software, Algorithms |
| Abstract: | We study the problems of processing single-source and two-point shortest path queries among weighted polygonal obstacles in the rectilinear plane. For the single-source case, we construct a data structure in O(n log&frac32; n) time and O(nlog n) space, where n is the number of obstacle vertices; this data structure enables us to report the length of a shortest path between the source and any query point in O(log n) time, and an actual shortest path in O(log n+k) time, where k is the number of edges on the output path. For the two-point case, we construct a data structure in O(n[SUP2]log[SUP2]n) time and space; this data structure enables us to report the length of a shortest path between two arbitrary query points in O(log[SUP2]n) time, and an actual shortest path in O(log[SUP2]n+k) time. Our work improves and generalizes the previously best-known results on computing rectilinear shortest paths among weighted polygonal obstacles. We also apply our techniques to processing two- point L[SUB1] shortest obstacle-avoiding path queries among arbitrary (i.e., not necessarily rectilinear) polygonal obstacles in the plane. No algorithm for processing two-point shortest path queries among weighted obstacles was previously known. [ABSTRACT FROM AUTHOR] |
| Copyright of SIAM Journal on Computing is the property of Society for Industrial & Applied Mathematics and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
Be the first to leave a comment!
