「《三角形分割》」の版間の差分
| 1行目: | 1行目: | ||
'''【さんかくけいぶんかつ (triangulation) 】''' | '''【さんかくけいぶんかつ (triangulation) 】''' | ||
| − | 点集合の三角形分割(triangulation)とは, 2次元においてはその凸包を2-単体 すなわち三角形に, 3次元では3-単体すなわち四面体に分割した構造である(四面体分割ともいう). | + | 点集合の三角形分割(triangulation)とは, 2次元においてはその凸包を2-単体 すなわち三角形に, 3次元では3-単体すなわち四面体に分割した構造である(四面体分割ともいう). 一般の次元の場合は単体分割あるいは簡単に三角形分割といわれる. 三角形分割は, 凸包・凸多面体とならんで基本的な幾何構造であり, 理論的に 重要であるだけでなく, コンピューターグラフィクスや有限要素解析・内挿でのメッシュ生成など広く応用がある. |
| − | + | <math>S=\{p_1,p_2,\ldots,p_n\}\, </math>を<math>d\, </math>次元の<math>n\, </math>点の集合, <math>\mbox{CH}(S)\, </math> を<math>S\, </math>の凸包とする. <math>S\, </math>の三角形分割<math>\tau= \{S_1,S_2, \dots ,S_m\}\, </math>と は, 次の条件を満たすものである. | |
:<math>\begin{array}{ll} | :<math>\begin{array}{ll} | ||
| − | 1. & | + | 1. & {\rm dim}\ {\rm CH}(S_i) = d, \ |S_i| = d+1, \ S_i\subseteq S \quad (i = 1,2,\dots,m) \\ |
| − | 2. & \bigcup_{i=1}^m {\rm CH}(S_i) = {\rm CH}(S) | + | 2. & \bigcup_{i=1}^m {\rm CH}(S_i) = {\rm CH}(S) \\ |
| − | 3. & | + | 3. & {\rm CH}(S_i)\cap{\rm CH}(S_j)={\rm CH}(S_i\cap S_j) \ (i \neq j) |
| − | \end{array}</math> | + | \end{array}\, </math> |
| − | 平面上の一般の位置にある点集合 | + | 平面上の一般の位置にある点集合<math>S\, </math>と<math>S\, </math>の点をすべて用いる三角形分割を考える. <math>S\, </math>のどの三角形分割も, オイラー(L. Euler)の公式から同じ数の三角形をもつ. また, 三角形分割の個数については, 三角形分割の平面性に着目して解析することにより <math>{\rm O}(2^{{\rm O}(n)})\, </math>であることがいえる. 凸<math>n\, </math>角形の頂点の場合は, 三角形分割の個数は<math>\frac{1}{n-1}{2n-4\choose n-2}\, </math>である. 動的計画法を用いることにより, 多角形内部の三角形分割の数を数える ことは多項式時間で行えるが, 一般の点集合の三角形分割の個数を多項式時間 で数えることができるかどうかは未解決の問題である. 多数の三角形分割の中から1つ選ぶ際の基準として代表的なものを上げる. |
1. (最小角最大) 三角形分割での全角度の最小のもの(最小角)を最大にする | 1. (最小角最大) 三角形分割での全角度の最小のもの(最小角)を最大にする | ||
| 23行目: | 23行目: | ||
4. (最大最小包含円最小) 三角形分割の各三角形の最小包含円(鈍角三角形の場合, 鈍角の対辺を直径にする円)のうち最大のものを最小にする | 4. (最大最小包含円最小) 三角形分割の各三角形の最小包含円(鈍角三角形の場合, 鈍角の対辺を直径にする円)のうち最大のものを最小にする | ||
| − | 5. (最大アスペクト比最小) 三角形分割の各三角形のアスペクト比( | + | 5. (最大アスペクト比最小) 三角形分割の各三角形のアスペクト比(三角形の外接円半径と内接円半径の比)の最大のものを最小にする |
| − | + | 他にも色々な評価規準が考えられる. 以下で述べるドロネー三角形分割は, このうち最小角最大, 最大包含円最小という性質を満たし(最大外接円最小も), かつ<math>{\rm O}(n\log n)\, </math>の高速の時間で求めることができる. 最大角を最小にする<math>{\rm O}(n^2\log n\, </math>)時間の動的計画法を用いたアルゴリズム も知られている. 一方, 辺長和を最小にする[[重み最小三角形分割]] 問題の複雑さについてはまだよくわかっていないが, 2次元の場合は解法が与えられている. 点集合が凸<math>n\, </math>角形の頂点集合の場合, 辺長和最小問題は動的計画法によって <math>{\rm O}(n^3)\, </math>時間で解ける. アスベクト比最適化なども含めた整数計画によるアプローチも はかられている. | |
| − | 三角形分割を応用上も役立つものにしているのは, ドロネー三角形分割あるいは[[ドロネー図]]である. これはボロノイ図の双対グラフとして定義される. ここでは, アルゴリズム的にも 有用な定義を与えておく. 2次元の点 | + | 三角形分割を応用上も役立つものにしているのは, ドロネー三角形分割あるいは[[ドロネー図]]である. これはボロノイ図の双対グラフとして定義される. ここでは, アルゴリズム的にも 有用な定義を与えておく. 2次元の点<math>p_i=(x_i,y_i) (i=1,\cdots,n)\, </math>に対して, 新たに<math>z\, </math>軸を考え, 3次元の点<math>p'_i=(x_i,y_i,x_i^2+y_i^2)\, </math>を対応させる. このとき, <math>p'_i (i=1,\cdots,n)\, </math>の3次元の凸包の<math>z\, </math>軸に関する下側境界 を<math>(x,y)\, </math>平面に正射影したものを, <math>p_i\, </math> <math>(i=1,\ldots,n)\, </math>のドロネー図 と定める. |
| − | ドロネー三角形分割は, 各三角形の外接円が他の点を内部に含まない三角形分割 として特徴づけられる. ドロネー三角形分割でないと, 点集合の中で凸四角形 <math> | + | ドロネー三角形分割は, 各三角形の外接円が他の点を内部に含まない三角形分割 として特徴づけられる. ドロネー三角形分割でないと, 点集合の中で凸四角形 <math>p_1,p_2,p_3,p_4\, </math>の三角形分割で, その三角形の外接円が他の点を含んでいる ものが存在する. このとき使っている対角線をもう1つの対角線に取り換えると, 局 所的に外接円に残りの1つの点は入らなくなる. 対角線を入れ換えることを対角変形といい, このように局所的にドロネー図に近付ける方向をドロネー対角変形と いう. 2次元では任意の三角形分割から<math>{\rm O}(n^2)\, </math>回ドロネー対角変形を行なう ことで, 必ずドロネー三角形分割に変換できる. |
ドロネー三角形分割は, 上述のような様々な最適化基準を満たすが, その多く はこのドロネー対角変形によりその基準が改善されるという論法で証明され る. その場合, 最小角最大を例にすると, 全ての角度を小さい順に並べたベク トルについて, ドロネー三角形分割は辞書式順序で最小なベクトルを与えることも示すことができる. | ドロネー三角形分割は, 上述のような様々な最適化基準を満たすが, その多く はこのドロネー対角変形によりその基準が改善されるという論法で証明され る. その場合, 最小角最大を例にすると, 全ての角度を小さい順に並べたベク トルについて, ドロネー三角形分割は辞書式順序で最小なベクトルを与えることも示すことができる. | ||
| − | 三角形分割を2変数関数 | + | 三角形分割を2変数関数<math>f\, </math>の内挿関数<math>g\, </math>に適用した際, 曲面の三角形パッチによる近似の粗さの度合を |
| − | <math> | + | <math> {\sum}_{S_i\in\tau}\int_{S_i} |
\left[ | \left[ | ||
\left(\partial g/\partial x\right)^2+ | \left(\partial g/\partial x\right)^2+ | ||
\left(\partial g/\partial y\right)^2 | \left(\partial g/\partial y\right)^2 | ||
\right]{\rm d}x{\rm d}y | \right]{\rm d}x{\rm d}y | ||
| − | + | \, </math> | |
で定義すると, ドロネー対角変形は粗さ度を改善し, 最適性が導かれる. 最大最小包含円最小性は, 放物線のポテンシャル関数の性質によっている. | で定義すると, ドロネー対角変形は粗さ度を改善し, 最適性が導かれる. 最大最小包含円最小性は, 放物線のポテンシャル関数の性質によっている. | ||
高次元の三角形分割の構造は一般に難しい. 三角形(単体)の個数も一定ではなく, 一般化された高次元対角変形により任意の三角形分割間で変換できるかどうかもわかっ ていない. 3次元で, 非凸の多面体の内部を新しい点を導入することなく四面体に分割することができるかどうかという問題は, [[NP困難]]である. | 高次元の三角形分割の構造は一般に難しい. 三角形(単体)の個数も一定ではなく, 一般化された高次元対角変形により任意の三角形分割間で変換できるかどうかもわかっ ていない. 3次元で, 非凸の多面体の内部を新しい点を導入することなく四面体に分割することができるかどうかという問題は, [[NP困難]]である. | ||
| − | 高次元三角形分割の性質のよい有用な部分クラスとして, 正則三角形分割(regular triangulation)がある. これは, 点集合 | + | 高次元三角形分割の性質のよい有用な部分クラスとして, 正則三角形分割(regular triangulation)がある. これは, 点集合<math>S\, </math>に対して新たなもう1次元方向を考え, その方向に各点に高さを与え, その分だけ新しい次元方向に持ち上げた点集合の凸包の下側境界を元の空間に正射影することにより得られるものである. もし, その凸包の下側境界にすべてのもち上げられた点がのっており, さらにそれらが一般の位置にあれば, 正射影されたものはまさしくこれまでの定義の三角形分割である. 正則三角形分割では与えられた点で三角形分割の頂点として使われないものもある. 2次元でも正則でない三角形分割は存在する. |
ドロネー三角形分割は正則であり, 正則三角形分割は高次元の場合も任意の2つの正則三角形分割は一般化対角変形で変換することができ, 2次元の三角形分割に通じるよい性質をもっている. さらに, 正則三角形分割は凸多面体と密接な関係をもった概念で, 数学・組合せ論で色々な展開が図られている. 詳細は [1] 参照. | ドロネー三角形分割は正則であり, 正則三角形分割は高次元の場合も任意の2つの正則三角形分割は一般化対角変形で変換することができ, 2次元の三角形分割に通じるよい性質をもっている. さらに, 正則三角形分割は凸多面体と密接な関係をもった概念で, 数学・組合せ論で色々な展開が図られている. 詳細は [1] 参照. | ||
2007年7月6日 (金) 22:03時点における版
【さんかくけいぶんかつ (triangulation) 】
点集合の三角形分割(triangulation)とは, 2次元においてはその凸包を2-単体 すなわち三角形に, 3次元では3-単体すなわち四面体に分割した構造である(四面体分割ともいう). 一般の次元の場合は単体分割あるいは簡単に三角形分割といわれる. 三角形分割は, 凸包・凸多面体とならんで基本的な幾何構造であり, 理論的に 重要であるだけでなく, コンピューターグラフィクスや有限要素解析・内挿でのメッシュ生成など広く応用がある.
を次元の点の集合, をの凸包とする. の三角形分割と は, 次の条件を満たすものである.
平面上の一般の位置にある点集合構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle S\, }
と構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle S\, }
の点をすべて用いる三角形分割を考える. 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle S\, }
のどの三角形分割も, オイラー(L. Euler)の公式から同じ数の三角形をもつ. また, 三角形分割の個数については, 三角形分割の平面性に着目して解析することにより 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle {\rm O}(2^{{\rm O}(n)})\, }
であることがいえる. 凸構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle n\, }
角形の頂点の場合は, 三角形分割の個数は構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \frac{1}{n-1}{2n-4\choose n-2}\, }
である. 動的計画法を用いることにより, 多角形内部の三角形分割の数を数える ことは多項式時間で行えるが, 一般の点集合の三角形分割の個数を多項式時間 で数えることができるかどうかは未解決の問題である. 多数の三角形分割の中から1つ選ぶ際の基準として代表的なものを上げる.
1. (最小角最大) 三角形分割での全角度の最小のもの(最小角)を最大にする
2. (最大角最小) 三角形分割での全角度の最大のもの(最大角)を最小にする
3. (重み最小) 三角形分割の辺長の総和を最小にする
4. (最大最小包含円最小) 三角形分割の各三角形の最小包含円(鈍角三角形の場合, 鈍角の対辺を直径にする円)のうち最大のものを最小にする
5. (最大アスペクト比最小) 三角形分割の各三角形のアスペクト比(三角形の外接円半径と内接円半径の比)の最大のものを最小にする
他にも色々な評価規準が考えられる. 以下で述べるドロネー三角形分割は, このうち最小角最大, 最大包含円最小という性質を満たし(最大外接円最小も), かつ構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle {\rm O}(n\log n)\, } の高速の時間で求めることができる. 最大角を最小にする構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle {\rm O}(n^2\log n\, } )時間の動的計画法を用いたアルゴリズム も知られている. 一方, 辺長和を最小にする重み最小三角形分割 問題の複雑さについてはまだよくわかっていないが, 2次元の場合は解法が与えられている. 点集合が凸構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle n\, } 角形の頂点集合の場合, 辺長和最小問題は動的計画法によって 時間で解ける. アスベクト比最適化なども含めた整数計画によるアプローチも はかられている.
三角形分割を応用上も役立つものにしているのは, ドロネー三角形分割あるいはドロネー図である. これはボロノイ図の双対グラフとして定義される. ここでは, アルゴリズム的にも 有用な定義を与えておく. 2次元の点に対して, 新たに構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle z\, } 軸を考え, 3次元の点構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle p'_i=(x_i,y_i,x_i^2+y_i^2)\, } を対応させる. このとき, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle p'_i (i=1,\cdots,n)\, } の3次元の凸包の構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle z\, } 軸に関する下側境界 を構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (x,y)\, } 平面に正射影したものを, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle p_i\, } のドロネー図 と定める.
ドロネー三角形分割は, 各三角形の外接円が他の点を内部に含まない三角形分割 として特徴づけられる. ドロネー三角形分割でないと, 点集合の中で凸四角形 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle p_1,p_2,p_3,p_4\, } の三角形分割で, その三角形の外接円が他の点を含んでいる ものが存在する. このとき使っている対角線をもう1つの対角線に取り換えると, 局 所的に外接円に残りの1つの点は入らなくなる. 対角線を入れ換えることを対角変形といい, このように局所的にドロネー図に近付ける方向をドロネー対角変形と いう. 2次元では任意の三角形分割から構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle {\rm O}(n^2)\, } 回ドロネー対角変形を行なう ことで, 必ずドロネー三角形分割に変換できる.
ドロネー三角形分割は, 上述のような様々な最適化基準を満たすが, その多く はこのドロネー対角変形によりその基準が改善されるという論法で証明され る. その場合, 最小角最大を例にすると, 全ての角度を小さい順に並べたベク トルについて, ドロネー三角形分割は辞書式順序で最小なベクトルを与えることも示すことができる.
三角形分割を2変数関数構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f\, } の内挿関数構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle g\, } に適用した際, 曲面の三角形パッチによる近似の粗さの度合を 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle {\sum}_{S_i\in\tau}\int_{S_i} \left[ \left(\partial g/\partial x\right)^2+ \left(\partial g/\partial y\right)^2 \right]{\rm d}x{\rm d}y \, } で定義すると, ドロネー対角変形は粗さ度を改善し, 最適性が導かれる. 最大最小包含円最小性は, 放物線のポテンシャル関数の性質によっている.
高次元の三角形分割の構造は一般に難しい. 三角形(単体)の個数も一定ではなく, 一般化された高次元対角変形により任意の三角形分割間で変換できるかどうかもわかっ ていない. 3次元で, 非凸の多面体の内部を新しい点を導入することなく四面体に分割することができるかどうかという問題は, NP困難である.
高次元三角形分割の性質のよい有用な部分クラスとして, 正則三角形分割(regular triangulation)がある. これは, 点集合構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle S\, } に対して新たなもう1次元方向を考え, その方向に各点に高さを与え, その分だけ新しい次元方向に持ち上げた点集合の凸包の下側境界を元の空間に正射影することにより得られるものである. もし, その凸包の下側境界にすべてのもち上げられた点がのっており, さらにそれらが一般の位置にあれば, 正射影されたものはまさしくこれまでの定義の三角形分割である. 正則三角形分割では与えられた点で三角形分割の頂点として使われないものもある. 2次元でも正則でない三角形分割は存在する.
ドロネー三角形分割は正則であり, 正則三角形分割は高次元の場合も任意の2つの正則三角形分割は一般化対角変形で変換することができ, 2次元の三角形分割に通じるよい性質をもっている. さらに, 正則三角形分割は凸多面体と密接な関係をもった概念で, 数学・組合せ論で色々な展開が図られている. 詳細は [1] 参照.
参考文献
[1] 今井桂子, 「三角形分割全体の離散構造」, 『離散構造とアルゴリズムVI』 (藤重悟編), 近代科学社, 1999.