WEKO3
-
RootNode
アイテム
逆探索による三角形分割の列挙とその応用
https://ipsj.ixsq.nii.ac.jp/records/32419
https://ipsj.ixsq.nii.ac.jp/records/32419f729e369-1cdc-464f-8fba-21843b6c395f
名前 / ファイル | ライセンス | アクション |
---|---|---|
![]() |
Copyright (c) 1994 by the Information Processing Society of Japan
|
|
オープンアクセス |
Item type | SIG Technical Reports(1) | |||||||
---|---|---|---|---|---|---|---|---|
公開日 | 1994-05-13 | |||||||
タイトル | ||||||||
タイトル | 逆探索による三角形分割の列挙とその応用 | |||||||
タイトル | ||||||||
言語 | en | |||||||
タイトル | THE ENUMERATION OF TRIANGULATIONS BY REVERSE SEARCH AND ITS APPLICATIONS | |||||||
言語 | ||||||||
言語 | jpn | |||||||
資源タイプ | ||||||||
資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
資源タイプ | technical report | |||||||
著者所属 | ||||||||
東京大学理学部情報科学科 | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Department of Information Science, Faculty of Science, The University of Tokyo | ||||||||
著者名 |
京田, 芳明
× 京田, 芳明
|
|||||||
著者名(英) |
Yoshiaki, Kyoda
× Yoshiaki, Kyoda
|
|||||||
論文抄録 | ||||||||
内容記述タイプ | Other | |||||||
内容記述 | 三角形分割の組合せ的構造とそれに関連した最適化問題は計算幾何学において研究されてきたが、それは三角形分割がコンピューターグラフィクスにおけるメッシュ生成や有限要素分析に有用だからである。本論文は最初に平面上の点集合に対する三角形分割の数を逆探索アルゴリズムの計算実験をすることにより調べる。凸n角形では分割総数は[numerical format]であり、正方形内にランダムにおかれた点集合の分割総数はそれに近いことが実験的に示される。また、平面上の三角形分割に関する最適化問題についても列挙アルゴリズムを用いてしらべる。正方形内に一様にランダムにある点集合に対して、そのDelaunay分割が最小辺長になっている確率は点集合の大きさの増加とともに減少することが観察される。 | |||||||
論文抄録(英) | ||||||||
内容記述タイプ | Other | |||||||
内容記述 | The combinatorial structure of triangulations and related optimization problem have been considered in computational geometry, since triangulations are useful in the mesh generation algorithm in computer graphics and finite element analysis. This thesis first investigates the number of triangulations of a planer point set by computational experiments of a reverse-search algorithm. For a convex polygon of n vertices, the number of distinct triangulations is [numerical format]. The number of triangulations of points randomly distributed in the square is computationally shown to be close to the above number. Some optimization problems concerning planer triangulations are also investigated by using enumeration algorithm. It is observed that for random points uniformly distributed in the square, the probability that Delaunay triangulation is a minimum-length triangulation decreases as the size of points increases. | |||||||
書誌レコードID | ||||||||
収録物識別子タイプ | NCID | |||||||
収録物識別子 | AN1009593X | |||||||
書誌情報 |
情報処理学会研究報告アルゴリズム(AL) 巻 1994, 号 35(1994-AL-039), p. 25-31, 発行日 1994-05-13 |
|||||||
Notice | ||||||||
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
出版者 | ||||||||
言語 | ja | |||||||
出版者 | 情報処理学会 |