Rectilinear Shortest Paths in a Rectilinear Simple Polygon
Summary :
We consider the following two fundamental problems: (P1) We are given a rectilinear simple polygon P with n edges and a point s in its interior. Given a query point t in the interior of P, find a rectilinear shortest path between s and t. (P2) We are given a rectilinear simple polygon P with n edges. Given a query point pair (s,t) in the interior of P, find a rectilinear shortest path between s and t. For the problem P1, we present an efficient algorithm which works in O(log n+L) query time and O(n log n) preprocessing time, where L is the number of line segments in the shortest path. Another important thing is that the shortest path obtained by the algorithm is of the minimum bends among all the paths between the two points. If only the distance between s and t is needed, then O(log n) time is enough for the query. On the other hand, for the problem P2, O(n) query time is needed while the preprocessing time is the same. Based on the algorithms, it is shown that given m points in a rectilinear n-edge simple polygon we can compute the distance between every pair of points in O(m(m+n)+nlog n) time.
- Publication
- IEICE TRANSACTIONS on transactions Vol.E69-E No.6 pp.750-758
- Publication Date
- 1986/06/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- PAPER
- Category
- Algorithm, Computational Complexity
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Tetsuo ASANO, "Rectilinear Shortest Paths in a Rectilinear Simple Polygon" in IEICE TRANSACTIONS on transactions,
vol. E69-E, no. 6, pp. 750-758, June 1986, doi: .
Abstract: We consider the following two fundamental problems: (P1) We are given a rectilinear simple polygon P with n edges and a point s in its interior. Given a query point t in the interior of P, find a rectilinear shortest path between s and t. (P2) We are given a rectilinear simple polygon P with n edges. Given a query point pair (s,t) in the interior of P, find a rectilinear shortest path between s and t. For the problem P1, we present an efficient algorithm which works in O(log n+L) query time and O(n log n) preprocessing time, where L is the number of line segments in the shortest path. Another important thing is that the shortest path obtained by the algorithm is of the minimum bends among all the paths between the two points. If only the distance between s and t is needed, then O(log n) time is enough for the query. On the other hand, for the problem P2, O(n) query time is needed while the preprocessing time is the same. Based on the algorithms, it is shown that given m points in a rectilinear n-edge simple polygon we can compute the distance between every pair of points in O(m(m+n)+nlog n) time.
URL: https://global.ieice.org/en_transactions/transactions/10.1587/e69-e_6_750/_p
Copy
@ARTICLE{e69-e_6_750,
author={Tetsuo ASANO, },
journal={IEICE TRANSACTIONS on transactions},
title={Rectilinear Shortest Paths in a Rectilinear Simple Polygon},
year={1986},
volume={E69-E},
number={6},
pages={750-758},
abstract={We consider the following two fundamental problems: (P1) We are given a rectilinear simple polygon P with n edges and a point s in its interior. Given a query point t in the interior of P, find a rectilinear shortest path between s and t. (P2) We are given a rectilinear simple polygon P with n edges. Given a query point pair (s,t) in the interior of P, find a rectilinear shortest path between s and t. For the problem P1, we present an efficient algorithm which works in O(log n+L) query time and O(n log n) preprocessing time, where L is the number of line segments in the shortest path. Another important thing is that the shortest path obtained by the algorithm is of the minimum bends among all the paths between the two points. If only the distance between s and t is needed, then O(log n) time is enough for the query. On the other hand, for the problem P2, O(n) query time is needed while the preprocessing time is the same. Based on the algorithms, it is shown that given m points in a rectilinear n-edge simple polygon we can compute the distance between every pair of points in O(m(m+n)+nlog n) time.},
keywords={},
doi={},
ISSN={},
month={June},}
Copy
TY - JOUR
TI - Rectilinear Shortest Paths in a Rectilinear Simple Polygon
T2 - IEICE TRANSACTIONS on transactions
SP - 750
EP - 758
AU - Tetsuo ASANO
PY - 1986
DO -
JO - IEICE TRANSACTIONS on transactions
SN -
VL - E69-E
IS - 6
JA - IEICE TRANSACTIONS on transactions
Y1 - June 1986
AB - We consider the following two fundamental problems: (P1) We are given a rectilinear simple polygon P with n edges and a point s in its interior. Given a query point t in the interior of P, find a rectilinear shortest path between s and t. (P2) We are given a rectilinear simple polygon P with n edges. Given a query point pair (s,t) in the interior of P, find a rectilinear shortest path between s and t. For the problem P1, we present an efficient algorithm which works in O(log n+L) query time and O(n log n) preprocessing time, where L is the number of line segments in the shortest path. Another important thing is that the shortest path obtained by the algorithm is of the minimum bends among all the paths between the two points. If only the distance between s and t is needed, then O(log n) time is enough for the query. On the other hand, for the problem P2, O(n) query time is needed while the preprocessing time is the same. Based on the algorithms, it is shown that given m points in a rectilinear n-edge simple polygon we can compute the distance between every pair of points in O(m(m+n)+nlog n) time.
ER -
English
