正方形の頂点と最短距離

シュタイナー木問題

いくつかの点が与えられた時にその点たちをうまく連結させることを考えます。

連結させるときに使う線分の長さが最小になるような方法を求める問題をシュタイナー木問題と言います。

例えば，点たちを「都市」，連結させるときに使う線分を「道路」に見立ててみると，いくつかの都市を結ぶ最短の道路網を構成する問題になります。

例えば，1つの点を発電所，残りの点たちを「家」，連結させるときに使う線分を「電線」に見立てると，使う電線の長さ最小で家々に電気を配給する問題になります。（電柱は何本使っても構いません）

三点の場合のシュタイナー木問題

本題に入る前に，三点 $A,B,C$ を結ぶシュタイナー木問題考えてみます。

$\angle A$ が最大だとしても一般性を失いません。（このとき $BC$ が三角形 $ABC$ の最大辺となる）

素朴に思いつくのは線分 $AB, AC$ を引く方法ですが，実は三角形の内部にうまく点 $P$ を選んで $PA,PB,PC$ を結ぶとより小さくできる場合があります。つまり，$AB+AC > PA+PB+PC$ となる場合があります。（図において青線で結ぶより赤線で結ぶ方がお得！）

$P$ をフェルマー点と呼ばれる点( $\angle APB=\angle BPC=\angle CPA=120^{\circ}$ を満たす点)に取れば線分和が最小になることが分かります。→三角形のフェルマー点の3通りの証明

以降はフェルマー点の考え方をもとに正方形の問題を扱います。

正方形の頂点を最短距離で結ぶ

愚直な方法：一辺が1の正方形の三辺を選んで結ぶと長さの和は3になります。（上の図）

少し工夫した方法：真ん中に分岐点を1つ作って $X$ 型に結ぶと長さの和は $2\sqrt{2}\simeq 2.8$ になります。（まん中の図）

更に工夫した方法： $X$ 型の図の下側の三角形と上側の三角形に注目してそれぞれフェルマー点に分岐点を作ります。結果的に分岐点は2つになります。（下の図）分岐点の周りの角度が全て $120^{\circ}$ であることに注意して長さの総和を計算すると $1+\sqrt{3}\simeq 2.7$ となります。

緑の図が最短であることの証明

実際に $1+\sqrt{3}$ の解が最短であることは以下の手順で証明できます。

• 分岐点を2つに限れば $1+\sqrt{3}$ のものが最短
• 分岐点は2つ以下のものだけを考えれば十分

後者は直感的にはほとんど当たり前ですが厳密に書くとわりと難しいのでここでは前者を解説します。フェルマー点の導出方法を知っていたら比較的簡単に思いつく方法です。