2026-04-21T16:50:23Z https://ipsj.ixsq.nii.ac.jp/oai

oai:ipsj.ixsq.nii.ac.jp:00014100 2025-01-23T00:56:29Z 581:768:771

基礎理論 誤差による破綻の心配のない線分Voronoi図構成算法 A Failure - free Algorithm for Constructing Voronoi Diagrams of Line Segments 今井, 敏行 杉原, 厚吉 Toshiyuki, Ima Kokichi, Sugihara 論文 平面上の点の勢力圏を表す図であるVoronoi図を一般化することは、理諭的に興昧深いだけでなく、実用上も重要である。本論文では、線分Voronoi図の実用的な構成寡法を考案する。この新しい算法は、従来の逐次添加型の算法に、位相優先法と我々が呼んでいる数値誤差対策を適用したものである。この算法は、計算誤差による破綻を完全に防止でき、必ず結果が出力される、さらに、出力が本来持つはずの位相的な性質のいくつかが保証される。単精度浮動小数点程度の誤差が発生する環境では、線分数nに対して、理論的に従来並みのO(n2)の速度を確保することができ、最悪の場合でもO(n3)時間で処理を終了する。記億量はO（n）であり、理論的に最良である。また、算法を計算機上に実装し、実際こは、さらに高速に計算できることも計算機実験で確かめた。 journal article 1994-10-15 application/pdf 情報処理学会論文誌 10 35 1966 1977 1882-7764 AN00116647 https://ipsj.ixsq.nii.ac.jp/record/14100/files/IPSJ-JNL3510002.pdf jpn