■シャボン玉の科学(その77)
ユークリッドは三角形の中心と呼べる点を4つ(内心,重心,外心,垂心)知っていたらしいのですが,これ以外にも中心はいろいろあります.
微分積分の入門書に「平面上に3つの定点A,B,Cがある.この平面上に点Pをとって,AP^2+BP^2+CP^2が最小になるようにせよ」という問題が偏導関数の応用例として載せられています.その点Pは重心です.3定点が4定点であっても,同じ議論になるのですが,距離の2乗の和に特に具体的な意味があるようには思えません.むしろ,2乗を取り去ったほうが問題としては自然です.
そこで,「A,B,C3軒の家に電線をひきたい.電線の長さを最小にするにはどこの柱を立てればよいか」ではAP+BP+CPを最小にする実用価値のある問題になります.
===================================
1辺の長さが1の正三角形の頂点を考えてみる.正三角形の2辺に沿ってA→B→Cと電線をはわせると,電線の長さは2になる.しかし,正三角形の重心と3つの頂点のそれぞれとを結ぶことを考えると,電線の長さは√3で済む.
一般の三角形についてのこの問題は17世紀のフランスの数学者フェルマーがイタリアの物理学者トリチェリ,数学者カヴァリエリに出題したものとして有名な問題で,求める点Pをフェルマー点(またはトリチェリ点,シュタイナー点)といいます.点Pは三角形ABCの内部にありますが,∠A,∠B,∠C<120°のときには,3頂点に至る距離の和が最小となる点は3辺を等角120°に見込む点です.∠A,∠B,∠Cのいずれかが≧120°のときには,それぞれ頂点A,頂点B,頂点Cになります.
このフェルマー点は頂点と外正三角形の頂点を結ぶ直線の共点として得られます.すなわち,フェルマー点を見つけるには与えられた三角形の各辺の上に正三角形を立てて各頂点と結ぶと,これら3本の線は1点Fで交わり∠AFB=∠BFC=∠CFAが成り立ちます.また,フェルマー点は3つの正三角形の外接円の交点でもあります.
===================================
さらに一般の位置にある頂点の集合についてはどうだろうか? 1辺の長さが1の正方形の4つの頂点の場合でさえ,最短結線の仕方は自明ではない.正方形の3辺に沿ってA→B→C→Dと電線をはわせると,電線の長さは3になる.しかし,2点を加えると1+√3が最短となることがわかっている.これ以上点を加えたとしても短くはならないのである.
以下に,長さの総和を最短にする平面石鹸膜の3点,4点シュタイナー問題の解を示す.
任意のN点において、extravertexは最大でN-2点存在する。 例として、N=3では1点、N=4では2点。
===================================
それでは7×7格子,もっと一般にn×n格子の場合はどうなるだろうか? このような最短配線問題は最小木問題(問題の発案者シュタイナーに因んで最小シュタイナー木問題)と呼ばれていますが,VLSI回路を設計するときの最も基本的な技術となっています.
===================================