{"updated":"2025-01-22T16:15:20.962558+00:00","metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00032250","sets":["1164:2592:2666:2671"]},"path":["2671"],"owner":"1","recid":"32250","title":["警備員経路アルゴリズムの時間解析について"],"pubdate":{"attribute_name":"公開日","attribute_value":"1997-01-23"},"_buckets":{"deposit":"51ae9012-05d5-4e33-875a-4ef5cb31857e"},"_deposit":{"id":"32250","pid":{"type":"depid","value":"32250","revision_id":0},"owners":[1],"status":"published","created_by":1},"item_title":"警備員経路アルゴリズムの時間解析について","author_link":["0","0"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"警備員経路アルゴリズムの時間解析について"},{"subitem_title":"On the time analysis of watchman route algorithms","subitem_title_language":"en"}]},"item_type_id":"4","publish_date":"1997-01-23","item_4_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"東海大学開発工学部"},{"subitem_text_value":"名古屋大学工学部"}]},"item_4_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"School of High - Technology for Human Welfare, Tokai University","subitem_text_language":"en"},{"subitem_text_value":"School of Engineering, Nagoya University","subitem_text_language":"en"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"jpn"}]},"item_publisher":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"情報処理学会","subitem_publisher_language":"ja"}]},"publish_status":"0","weko_shared_id":-1,"item_file_price":{"attribute_name":"Billing file","attribute_type":"file","attribute_value_mlt":[{"url":{"url":"https://ipsj.ixsq.nii.ac.jp/record/32250/files/IPSJ-AL96055007.pdf"},"date":[{"dateType":"Available","dateValue":"1999-01-23"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-AL96055007.pdf","filesize":[{"value":"592.1 kB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"660","billingrole":"5"},{"tax":["include_tax"],"price":"330","billingrole":"6"},{"tax":["include_tax"],"price":"0","billingrole":"9"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_date","version_id":"f02df045-3a4a-489b-a065-c2496a781d80","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 1997 by the Information Processing Society of Japan"}]},"item_4_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"譚, 学厚"},{"creatorName":"平田, 富夫"}],"nameIdentifiers":[{}]}]},"item_4_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Xuehou, Tan","creatorNameLang":"en"},{"creatorName":"Tomio, Hirata","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_4_source_id_9":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AN1009593X","subitem_source_identifier_type":"NCID"}]},"item_4_textarea_12":{"attribute_name":"Notice","attribute_value_mlt":[{"subitem_textarea_value":"SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc."}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourceuri":"http://purl.org/coar/resource_type/c_18gh","resourcetype":"technical report"}]},"item_4_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"警備員経路問題とは、与えられた多角形Pに対し、Pの任意の点が経路上の少なくとも1点から見えるような最短の経路を見つけることである。この問題を解くいくつかのアルゴリズムが既に提案されている。しかし、これらのアルゴリズムの時間解析には誤りがあることが最近指摘された。それを直すため、本論文ではこれまでの時間解析を修正し、既存のアルゴリズムの正当性を示す。","subitem_description_type":"Other"}]},"item_4_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"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.","subitem_description_type":"Other"}]},"item_4_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicPageEnd":"60","bibliographic_titles":[{"bibliographic_title":"情報処理学会研究報告アルゴリズム（AL）"}],"bibliographicPageStart":"53","bibliographicIssueDates":{"bibliographicIssueDate":"1997-01-23","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"8(1996-AL-055)","bibliographicVolumeNumber":"1997"}]},"relation_version_is_last":true,"weko_creator_id":"1"},"created":"2025-01-18T23:01:23.122985+00:00","id":32250,"links":{}}