WEKO3
インデックスリンク
アイテム
Rectilinear shortest paths in a rectilinear simple polygon
https://doi.org/10.24517/00062802
https://doi.org/10.24517/0006280288c4f033-f309-4bde-b01c-7130b02a4a1f
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
TE-PR-ASANO-T-69-6-750-758.pdf (170.6 kB)
|
.png)
|
| Item type | 学術雑誌論文 / Journal Article(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2022-09-15 | |||||||
| タイトル | ||||||||
| タイトル | Rectilinear shortest paths in a rectilinear simple polygon | |||||||
| 言語 | ||||||||
| 言語 | eng | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||
| 資源タイプ | journal article | |||||||
| ID登録 | ||||||||
| ID登録 | 10.24517/00062802 | |||||||
| ID登録タイプ | JaLC | |||||||
| 著者 |
Asano, Tetsuo
× Asano, Tetsuo |
|||||||
| 著者別表示 |
浅野, 哲夫
× 浅野, 哲夫
|
|||||||
| 提供者所属 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 金沢大学 | |||||||
| 書誌情報 |
Transactions of the Institute of Electronics and Communication Engineers of Japan. Section E 巻 E69, 号 6, p. 750-758, 発行日 1986-06 |
|||||||
| ISSN | ||||||||
| 収録物識別子タイプ | ISSN | |||||||
| 収録物識別子 | 0387-236X | |||||||
| NCID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AA0086650X | |||||||
| 出版者 | ||||||||
| 出版者 | IEICE 電子情報通信学会 | |||||||
| 抄録 | ||||||||
| 内容記述タイプ | Abstract | |||||||
| 内容記述 | We consider the following two 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 problem P1, we present an efficient algorithm which works in O(log n plus L) query time and O(n log n) preprocessing time, where L is the number of line segments in the shortest path. The shortest path obtained by the algorithm is of 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. For 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 plus n) plus n log n) time. | |||||||
| 権利 | ||||||||
| 権利情報 | Copyright © IEICE 電子情報通信学会 | |||||||
| 著者版フラグ | ||||||||
| 出版タイプ | VoR | |||||||
| 出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 | |||||||
