ギルバート・ポラック予想

数学において、ギルバート・ポラック予想は、ユークリッド平面上の同じ点集合に対するシュタイナー木とユークリッド最小全域木の長さの比に関する未証明の予想である。これは1968年にエドガー・ギルバートとヘンリー・O・ポラックによって提唱された。 ^{[ 1 ]}具体的には、この予想は、ユークリッド平面上の任意の有限点集合に対して、ユークリッド最小全域木の長さが以下であることを述べている。${\displaystyle 2/{\sqrt {3}}}$シュタイナー最小木の長さの倍。^{[ 2 ]}

コンピュータサイエンスにおける未解決問題

ユークリッド平面のシュタイナー比は等しいか？${\displaystyle 2/{\sqrt {3}}}$？

コンピュータサイエンスにおける未解決問題

平面上の点の集合に対して、与えられた点のみを端点として点を結ぶ最短の線分ネットワークは、その集合のユークリッド最小全域木です。与えられた点集合には存在しない追加の端点を使用することで、より短いネットワークを構築できる場合があります。これらの追加の点はシュタイナー点と呼ばれ、それらを使用して構築できる最短のネットワークはシュタイナー最小木と呼ばれます。シュタイナー比は、すべての点集合について、ユークリッド最小全域木の長さとシュタイナー最小木の長さの比の上限です。シュタイナー最小木の方が短いため、この比は常に 1 より大きくなります。^{[ 2 ]}

シュタイナー比の下限は、一辺の長さが1の正三角形の頂点にある3つの点によって与えられます。これらの3つの点に対して、ユークリッド最小全域木は三角形の2つの辺を使用し、全長は2です。シュタイナー最小木は、これら3つの点を三角形の重心にあるシュタイナー点に接続し、全長はより短くなります。$\displaystyle {\sqrt {3}}}$この例から、シュタイナー比は少なくとも$2/√3 ≈ 1.155$[ ^{2 ]​}

ギルバート・ポラック予想は、この例がシュタイナー比の最悪のケースであり、この比率が${\displaystyle 2/{\sqrt {3}}}$つまり、ユークリッド平面上の任意の有限点集合に対して、ユークリッド最小全域木は以下の長さになることはない。${\displaystyle 2/{\sqrt {3}}}$シュタイナー最小木の長さの倍。^{[ 2 ]}

1990年、Ding-Zhu DuとFrank Kwang-Ming Hwangは証明^{[ 3 ] [ 2 ]}を発表したが、後に重大な欠陥があることが判明した^{[ 4 ] [ 5 ]。}

DuとHwangの欠陥のある結果に基づいて、J. Hyam RubinsteinとJia F. Wengは、Steiner比もまた${\displaystyle 2/{\sqrt {3}}}$定曲率の 2 次元球面の場合、^{[ 6 ]} Du と Hwang の基本結果にギャップがあるため、Rubinstein と Weng の結果もまだ証明されていないと考えられています。^{[ 7 ]}