ppt

第５節 Minimum hexagonal trees
hexa- = 「6」を表わす接頭語
hexagon = ６角形
Steiner tree
Hexagonal tree
与えられた３方向し
か使ってはいけない
Ls(P) = 与えられた点達 P を結ぶSteiner minimum tree の長さ
Lh(P) = 与えられた点達 P を結ぶ minimum hexagonal tree の
長さ
Lemma 12 (Weng).
Ls(P)≧√3/2 Lh(P)
証明. △ABCにおいて∠Ａ≧１２０°, BC≧√3/2 (AB+AC) を示す
A’
A
B
∠Ａ’ =１２０°となるまで点Aを移動する。
⇒ AB+AC ≦ A’B+A’C
C
A’, B, C を通る円を描くと、
C
A’
B
120°－θ
θ
C
A’
半径 r
B
120-θ
θ
A’B+A’C = 2r sin(θ/2)+ 2r sin(120-θ/2)
= 4r sin 30 cos (θ- 60/2)
= 2r cos (θ- 60/2)
≦ 2r
= 2/√3 BC
よって、AB+AC ≦ 2/√3 BC
（和積の公式）
（ sin 30 = 1/2）
A
B
C
与えられた３方向
Steiner treeの各辺を「BC」だと思って、与えられた３方向に
置き換える。
よって、Ls(P)≧√3/2 Lh(P)
Lemma 11より、特性領域 C(t*;x) は正３角形格子の一部
与える３方向は正三角形格子の３方向
C(t*;x)
例
C(t;x) は正三角形を２つつなげたもの
⇒ 特異構造である。
Ｑ．オレンジの線
(hexagonal tree)と赤
の線(MIST)の長さはど
ちらが短い？長い？
A．同じ長さ。
Minimum hexagonal tree を Γ(t*;x) の正三角形の辺へ押
しやると、minimum hexagonal treeの長さ＝MISTの長さ
Lemma 12 より、 Ls(P)≧√3/2 Lh(P)
⇒ （Steiner treeの長さ）≧√3/2 ×（MISTの長さ）
検証結果
１．(Lemma 1) Lt(x) = MISTの長さは連続ではない。
⇒ ft(x)=1- √3/2 Lt(x)の最小値が存在するか不明。
⇒ 特別なtopology t* の存在も不明。
２．Du-Hwangの功績
⇒ ft(x)の（最小）値とMI(t;x)の豊富さの関係を明らかにした。
例えば、Lemma 7. 『 MI(t*;y)が豊富ならば、yも最小点』
最終的に Lemma 10 で、特異構造（正三角形構造）
まで変形した。
１．(Lemma 1) Lt(x) = MISTの長さは連続ではない。
⇒ 特性領域 C(t;x) の定義を変えれば連続になるはず。
『C(t ; yk) →C(t; x)』がLemma 2の議論を成立させるために
必要。
最近届いたmail

Download Report