WEKO3
アイテム
警備員経路アルゴリズムの時間解析について
https://ipsj.ixsq.nii.ac.jp/records/32250
https://ipsj.ixsq.nii.ac.jp/records/32250c5b88a16-752c-4499-a678-b226c9bda651
名前 / ファイル | ライセンス | アクション |
---|---|---|
![]() |
Copyright (c) 1997 by the Information Processing Society of Japan
|
|
オープンアクセス |
Item type | SIG Technical Reports(1) | |||||||
---|---|---|---|---|---|---|---|---|
公開日 | 1997-01-23 | |||||||
タイトル | ||||||||
タイトル | 警備員経路アルゴリズムの時間解析について | |||||||
タイトル | ||||||||
言語 | en | |||||||
タイトル | On the time analysis of watchman route algorithms | |||||||
言語 | ||||||||
言語 | jpn | |||||||
資源タイプ | ||||||||
資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
資源タイプ | technical report | |||||||
著者所属 | ||||||||
東海大学開発工学部 | ||||||||
著者所属 | ||||||||
名古屋大学工学部 | ||||||||
著者所属(英) | ||||||||
en | ||||||||
School of High - Technology for Human Welfare, Tokai University | ||||||||
著者所属(英) | ||||||||
en | ||||||||
School of Engineering, Nagoya University | ||||||||
著者名 |
譚, 学厚
× 譚, 学厚
|
|||||||
著者名(英) |
Xuehou, Tan
× Xuehou, Tan
|
|||||||
論文抄録 | ||||||||
内容記述タイプ | Other | |||||||
内容記述 | 警備員経路問題とは、与えられた多角形Pに対し、Pの任意の点が経路上の少なくとも1点から見えるような最短の経路を見つけることである。この問題を解くいくつかのアルゴリズムが既に提案されている。しかし、これらのアルゴリズムの時間解析には誤りがあることが最近指摘された。それを直すため、本論文ではこれまでの時間解析を修正し、既存のアルゴリズムの正当性を示す。 | |||||||
論文抄録(英) | ||||||||
内容記述タイプ | Other | |||||||
内容記述 | The watchman route problem is to find a shortest route in a simple polygon such that each point in the interior of the polygon is visible from at least one point along the route. The best time bound for this problem among three existing watchman route algorithms is O(n^2), where n is the number of vertices of the given polygon. However, an error in the analysis of time complexities of those algorithms was recently pointed out. In this paper, we revise the method for analyzing the time complexities of the existing watchman route algorithms, and show that their time bounds are still correct. | |||||||
書誌レコードID | ||||||||
収録物識別子タイプ | NCID | |||||||
収録物識別子 | AN1009593X | |||||||
書誌情報 |
情報処理学会研究報告アルゴリズム(AL) 巻 1997, 号 8(1996-AL-055), p. 53-60, 発行日 1997-01-23 |
|||||||
Notice | ||||||||
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
出版者 | ||||||||
言語 | ja | |||||||
出版者 | 情報処理学会 |