WEKO3
アイテム
ユークリッド距離と回転角度を考慮した最短経路について
https://ipsj.ixsq.nii.ac.jp/records/30591
https://ipsj.ixsq.nii.ac.jp/records/3059148155148-c4e9-4d9c-8b62-ce10d899400d
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-PRO92011017.pdf (1.0 MB)
|
Copyright (c) 1993 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 1993-03-10 | |||||||
| タイトル | ||||||||
| タイトル | ユークリッド距離と回転角度を考慮した最短経路について | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | Finding Shortest Paths among Obstacles Using a Combined Euclidean Distance and Rotation Angle | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| 大阪大学基礎工学部情報工学科 | ||||||||
| 著者所属 | ||||||||
| 大阪大学基礎工学部情報工学科 | ||||||||
| 著者所属 | ||||||||
| 大阪大学基礎工学部情報工学科 | ||||||||
| 著者所属 | ||||||||
| 大阪大学基礎工学部情報工学科 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Information and Computer Sciences Faculty of Engineering Science, Osaka University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Information and Computer Sciences Faculty of Engineering Science, Osaka University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Information and Computer Sciences Faculty of Engineering Science, Osaka University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Information and Computer Sciences Faculty of Engineering Science, Osaka University | ||||||||
| 著者名 |
安留誠吾
× 安留誠吾
|
|||||||
| 著者名(英) |
Seigo, Yasutome
× Seigo, Yasutome
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 平面上の任意の2点間の最短経路を求める問題は，計算幾何学の基本的問題の一つである．本稿では，多角形の障害物と2点が与えられたとき，ユークリッド距離と回転角度の両方を考慮した評価尺度による最短経路をO（^2 log ）時間，O（^）領域で求めるアルゴリズムを提案する．また，始点と障害物が前もって与えられた場合にO（^2 log ）時間の前処理をしておけば，終点が与えられたときO（ log ）時間で最短経路が求められることも示す．ここでnは障害物の頂点の総数を表す． | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | The problem of finding the shortest path between two points in the plane is one of the fundamental problems in computational geometory. In this paper, given polygonal obstacles and two points, we present an algorithm for finding the shortest path in the new metric that combines the Euclidean distance and rotation angle. The algorithm runs in O(n^2 log n) time and O(n^2) space, where n is the number of the vertices of obstacles. When a source point and obstacles are pre-given, queries for the shortest path from the source point to a given point can be handled in O(n log n) time after O(n^2 log n) preprocessing. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN10485570 | |||||||
| 書誌情報 |
情報処理学会研究報告プログラミング（PRO） 巻 1993, 号 19(1992-PRO-011), p. 149-156, 発行日 1993-03-10 |
|||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
