制約つき3次元Delaunay図の構成算法

• Item type: SIG Technical Reports(1)
• 公開日: 1994-03-17
• タイトル: 制約つき3次元Delaunay図の構成算法
• タイトル / 言語: en
• タイトル: Three - Dimensional Constrained Delaunay Triangulation Algorithm
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 豊田工業高等専門学校情報工学科
• 著者所属: 東京大学工学部計数工学科
• 著者所属(英): en
• 著者所属(英): Department of Information and Computer Engineering Toyota National College of Technology
• 著者所属(英): en
• 著者所属(英): Department of Mathematical Engineering and Information Physics Faculty of Engineering, University of Tokyo
• 著者名: 稲垣, 宏; 杉原, 厚吉
• 著者名(英): Hiroshi, Inagaki; Kokichi, Sugihara
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 筆者らは，文献[1][2]において，位相構造を優先することで数値的安定化を図った3次元Voronoi図構成法を提案した．また，文献[3]では，このアルゴリズムを利用して，双対図形である3次元Delaunay図を生成する方法を提案した．本稿では，位相構造を優先させたVoronoi図構成法が，制約つきDelaunay図の構成にも利用できることを示す．ここで提案する算法では，制約を満たすように数値判定をねつ造しているために，正しいボロノイ図は出力されない．しかし，その双対を求めると，制約つきDelaunay図になっているのである．また，本算法を適用した3次元の制約つきDelaunay図構成プログラムを作成し，計算機実験により，その有効性を実証した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In our previous paper[2], we proposed a numerically robust algorithm for constructing the three-dimensional Voronoi diagram. In this paper, we show that this algorithm can be applied not only to the construction of the ordinary Delaunay triangulation but also to the construction of the constrained Delaunay triangulation. In order to construct the constrained Delaunay triangulation, we invent numerical results on the way to the construction of the Voronoi diagram in such a way that they satisfy the constraints. Moreover we implemented the algorithm as a computer program, and verified the validity of the algorithm by computational experiments.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1994, 号 26(1993-AL-038), p. 41-48, 発行日 1994-03-17
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会