誤差による破綻の心配のない線分Voronoi図構成算法

• Item type: Journal(1)
• 公開日: 1994-10-15
• タイトル: 誤差による破綻の心配のない線分Voronoi図構成算法
• タイトル / 言語: en
• タイトル: A Failure - free Algorithm for Constructing Voronoi Diagrams of Line Segments
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• その他タイトル / その他のタイトル: 基礎理論
• 著者所属: 東京大学工学部計数工学科
• 著者所属: 東京大学工学部計数工学科
• 著者所属(英): en
• 著者所属(英): Department of Mathematical Engineering and Information Physis, Faculty of Engineering, the University of Tokyo
• 著者所属(英): en
• 著者所属(英): Department of Mathematical Engineering and Information Physis, Faculty of Engineering, the University of Tokyo
• 著者名: 今井, 敏行; 杉原, 厚吉
• 著者名(英): Toshiyuki, Ima; Kokichi, Sugihara
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 平面上の点の勢力圏を表す図であるVoronoi図を一般化することは、理諭的に興昧深いだけでなく、実用上も重要である。本論文では、線分Voronoi図の実用的な構成寡法を考案する。この新しい算法は、従来の逐次添加型の算法に、位相優先法と我々が呼んでいる数値誤差対策を適用したものである。この算法は、計算誤差による破綻を完全に防止でき、必ず結果が出力される、さらに、出力が本来持つはずの位相的な性質のいくつかが保証される。単精度浮動小数点程度の誤差が発生する環境では、線分数nに対して、理論的に従来並みのO(n2)の速度を確保することができ、最悪の場合でもO(n3)時間で処理を終了する。記億量はO（n）であり、理論的に最良である。また、算法を計算機上に実装し、実際こは、さらに高速に計算できることも計算機実験で確かめた。
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 35, 号 10, p. 1966-1977, 発行日 1994-10-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764