組合せ構造を優先した多角形Voronoi図の構成法

• Item type: SIG Technical Reports(1)
• 公開日: 1995-05-12
• タイトル: 組合せ構造を優先した多角形Voronoi図の構成法
• タイトル / 言語: en
• タイトル: A Combinatorial - Structure Oriented Algorithm for Voronoi Diagrams of Polygons
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東京大学工学部
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, University of Tokyo
• 著者名: 今井, 敏行
• 著者名(英): Toshiyuki, Imai
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 点，線分，折れ線，多角形を生成元とするVoronoi図を構成する算法を示す．位相優先法に基づく線分Voronoi図の構成算法を拡張することによって実現した．図形のもつ組合せ構造を優先的に扱っている．一般の算法で正常な出力が得られる程度の計算精度の下では，この算法でも正常な出力を同等の計算量と記憶量で得ることができる．また，どのような計算精度の下でも正常終了し，出力が本来もつ組合せ構造のいくつかを保証する．この意味で本算法は計算誤差に対して強い．また誤差を前提にする算法であるため，入力が退化している状況でも算法は正常に働き，退化のための例外処理が不要である．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: An algorithm to construct Voronoi diagrams whose generators are points, line segments, chains and polygons is shown. This algorithm is adapted from a combinatorial-structure oriented algorithm for Voronoi diagrams of line segments. In this algorithm, Combinatorial structure of the diagrams is considered as prior information to numerical values. If the precision in computation is high enough for conventional algorithms to work well, this algorithm also constructs the correct Voronoi diagrams. Moreover, even when precision in computations is not enough, this algorithm ends up with a diagram as an output with several combinatorial properties which Voronoi diagrams must have. In this sense, this algorithm is robust against numerical error. This algorithm is designed in the assumption that numerical error exists; hence it has not any exceptional rules for degeneracy but still works for degenerate cases.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1995, 号 39(1995-AL-045), p. 17-24, 発行日 1995-05-12
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会