研究紹介: 3角形分割

3 角形分割の何がおもしろいか？

点配置を与えられたとき、それらの点のみを使ったその凸包の 3 角形分割（triangulation） は何通りかある。 例えば、凸 5 角形の頂点の点配置については、図の 5 つの 3 角形分割がある。

3 角形分割全体は、ただあるだけではなく、その中に構造を持っている。 例えば、先程の凸 5 角形の例では、 辺を一つだけ入れ替えることによって移り変われる （この操作は flip とよばれている）3角形分割が、 図の中で点線で結ばれている。] このような局所的な変更のみで移りあえるという関係について、 5 つの 3 角形分割は 5 角形の形をしたグラフの構造を持っていると言える。

一般次元において 3 角形分割全体がどのような構造を持つかを解明するのがわれわれの研究の目的である。

これまでの研究成果

（論文）

3角形分割の列挙

現在までの研究では、3 角形分割全体を効率的に列挙する手法を確立した。 また、実際にこのアルゴリズムを実行するプログラムを作成した。 3 角形分割の様子が数学的に興味深いような点配置は、 対称性のある点配置であることが多い。 このような対称性のある点配置について、 正則な 3 角形分割を効率的に列挙する手法も開発した。

3 角形分割と 3 角形分解の関係

3 角形分割においては、 分割の結果の各部分がきれいに接していることが求められる。 しかし、体積計算など一部の応用では、切り分けられれば十分であり、 接し方までは要求されない （このようなものを 3角形分解 simplicial decomposition とよぶ）。 この 2 つのクラスの違いについて、 最小 3 角形分解が最小 3 角形分割よりも少ない数の単体で済む例、 最大 3 角形分解が最大 3 角形分割よりも多くの単体を必要とする例、 3 角形分解における上限定理や下限定理などを示した。

単体的複体の逐次的分解についての性質

3 角形分割はより広く、単体的複体というクラスに属する。 単体的複体の逐次的な分解のしやすさについて、いくつかの性質が知られている。 これらの性質の間の関係を明らかにした。 コンピュータで幾何的なものを扱うとき、 このような逐次的な処理の可能性を考えることは大切である。

3 角形分割の応用

凸多面体を扱うとき、それをより小さなものに分割することによって、 より上手く扱えることは多い。 3 次元の点配置を扱う分野では 3 角形分割も必要になり、 それらの分野は、立体の表示を扱う 3 次元コンピュータ・グラフィックス、 シミュレーションにより計算を行う工学、 DNA の立体構造を扱う生物学など数多い。