曲線上に配置された母点に対する平均線形時間ボロノイ図構成法

• Item type: SIG Technical Reports(1)
• 公開日: 1997-01-23
• タイトル: 曲線上に配置された母点に対する平均線形時間ボロノイ図構成法
• タイトル / 言語: en
• タイトル: O (n) Average - Time Construction of the Voronoi Diagram for Generators on Smooth Curves
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東京大学大学院工学系研究科計数工学
• 著者所属: 東京大学大学院工学系研究科計数工学
• 著者所属(英): en
• 著者所属(英): Department of Mathematical Engineering and Information Physics, Graduate School of Engineering, University of Tokyo
• 著者所属(英): en
• 著者所属(英): Department of Mathematical Engineering and Information Physics, Graduate School of Engineering, University of Tokyo
• 著者名: 山田, 和公; 杉原, 厚吉
• 著者名(英): Kazuhiro, Yamada; Kokichi, Sugihara
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 曲線上に密に配置された母点に対するボロノイ図は，一般図形を生成元とするボロノイ図の近似として用いられる．従来の逐次添加法によってこのような母点配世に対するボロノイ図を構成すると，実際的に母点数の線形時間で構成することができない，誤判定を生じやすい，という困難が生じる．本報告では，この困難の原因を取り除くことによって，実際に母点数の線形時間でボロノイ図を構成する逐次添加法，および誤判定をより少なくする数値計算法を提案する．また，計算実験によってこの算法の有効性を確認する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The Voronoi diagram for generators on smooth curves is used for the approximation of the generalized Voronoi diagram for figures. Generators on smooth curves give difficulty in the construction of Voronoi diagram by the incremental method, because both construction time and numerical errors become larger. This paper proposes an O(n) average-time method for constructing the Voronoi diagram for generators densely distributed along curves and a method for computing numerical values more precisely. The parformance of the method is also evaluated experimentally.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1997, 号 8(1996-AL-055), p. 69-76, 発行日 1997-01-23
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会