ハイルブロンの三角形の問題

数学における未解決の問題:

正方形内の3 つの点のうち、面積が最大になるように点を選択した場合、その点によって決まる最小の三角形の面積の漸近的増加率はどれくらいですか。${\displaystyle n}$

（数学における未解決の問題がさらに増える）

離散幾何学とディスクレパンシー理論において、ハイルブロンの三角形問題とは、面積の小さい三角形を避けながら平面上に点を配置する問題である。この問題は、与えられた領域内に点をどのように配置しても、最小の三角形の面積はせいぜい点の数の2乗に反比例すると予想したハンス・ハイルブロンにちなんで名付けられた。彼の予想は誤りであることが証明されたが、最小三角形の面積の 漸近的増加率は未だ不明である。

ハイルブロンの三角形の問題は、与えられた数に対して、単位正方形や単位円板などの平面上の図形内の点の配置に関するものです。3つの点のそれぞれが三角形の 3 つの頂点を形成し、これらの三角形のうち面積で測った最小の三角形が問題となります。点の配置が異なれば最小の三角形も異なります。問題は、最小の三角形の面積を最大化するために点をどのように配置すればよいかを問うものです。 ^[1]${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$

より正式には、形状は平面上のコンパクト集合 であると仮定することができる。つまり、形状は原点から制限された距離内にとどまり、点をその境界上に配置することができる。この問題に関するほとんどの研究では、は面積がゼロでない凸集合でもある。配置された点のうち 3 つが直線 上にある場合、それらの点は面積がゼロと定義される退化した三角形を形成すると見なされ、最小の三角形を最大化する配置では点の共線的な 3 つが存在しない。形状がコンパクトであるという仮定は、最適性に近づく配置のシーケンスだけでなく、点の最適な配置が存在することを意味する。数は、この最適配置における最小の三角形の面積として定義することができる。^{[1] [a]}図に、単位正方形内に 6 つの点がある例を示します。これらの 6 つの点は異なる三角形を形成し、そのうち 4 つは図で網掛けされています。網掛けされた形状のうち 2 つを含む 20 個の三角形のうち 6 個の面積は 1/8 で、残りの 14 個の三角形の面積はそれよりも大きい。これは単位正方形における6つの点の最適な配置である。他の配置では、面積が1/8以下の三角形が少なくとも1つ形成される。したがって、. ^[2]${\displaystyle D}$${\displaystyle D}$${\displaystyle n}$${\displaystyle \Delta _{D}(n)}$${\displaystyle {\tbinom {6}{3}}=20}$${\displaystyle \Delta _{D}(6)={\tfrac {1}{8}}}$

研究者たちは特定の形状と少数の点についての値を研究してきましたが、 ^{[2] [3] [4]ハイルブロンは の}漸近的挙動に関心がありました。つまり、形状が固定されているが変化すると、最小の三角形の面積はとともにどのように変化するのでしょうか。つまり、ハイルブロンの疑問はの関数としての の成長率に関するものです。任意の 2 つの形状と について、と の数は定数倍のみ異なります。これは、内の点の配置は、内に収まるようにアフィン変換によって拡大縮小できるため、最小三角形面積は定数だけ変化するからです。したがって、 の成長率の境界でその成長の比例定数を省略すると、 の選択は無関係になり、下付き文字を省略できます。^[1]${\displaystyle \Delta _{D}(n)}$${\displaystyle D}$${\displaystyle n}$${\displaystyle n}$${\displaystyle \Delta _{D}(n)}$${\displaystyle n}$${\displaystyle D}$ ${\displaystyle D'}$${\displaystyle \Delta _{D}(n)}$${\displaystyle \Delta _{D'}(n)}$${\displaystyle n}$${\displaystyle D}$${\displaystyle D'}$${\displaystyle \Delta _{D}(n)}$${\displaystyle D}$

ハイルブロンは1951年以前に、三角形の最小面積は常に の関数として急速に縮小すると予想した。${\displaystyle n}$より具体的には、の2乗に反比例する。 ^{[1] [b]}${\displaystyle n}$ビッグオー記法では、これは次のように表現できる。 $${\displaystyle \Delta (n)=O\left({\frac {1}{n^{2}}}\right).}$$

反対に、ポール・エルデシュは、最小三角形面積がに${\displaystyle 1/n^{2}}$比例する点集合の例を見つけ、これが真実であれば、ハイルブロンの予想された境界を強化することはできないことを実証した。エルデシュは、これらの例を説明するために、一列に 3 つがない格子点の大きな集合について、一列に 3 つがない問題を定式化した。エルデシュが観察したように、 が素数のとき、整数格子上の点の集合( の場合)には 3 つの共線上の点が存在せず、したがってピックの公式により、それらが形成する各三角形の面積は少なくとも である。これらの格子点を単位正方形内に収まるように拡大すると、それらの最小三角形面積は に比例し、ハイルブロンの予想された上限と一致する。 が素数でない場合、 に近い素数を使用した同様の構成により、同じ漸近下限が得られる。^{[1] [c]}${\displaystyle n}$${\displaystyle n}$${\displaystyle (i,i^{2}{\bmod {n}})}$${\displaystyle n\times n}$ ${\displaystyle 0\leq i<n}$${\displaystyle {\tfrac {1}{2}}}$${\displaystyle 1/n^{2}}$${\displaystyle n}$${\displaystyle n}$

Komlós、Pintz、Szemerédi (1982) は、確率的手法を使用して、最小の三角形の面積が Erdős が見つけたものよりも大きい点の集合を見つけることで、最終的に Heilbronn の予想を反証しました。それらの構築には、次の手順が含まれます。

• 単位正方形内に点をランダムに配置します。${\displaystyle n^{1+\varepsilon }}$${\displaystyle \varepsilon >0}$
• 予想外に近いポイントのペアをすべて削除します。
• 残りの低面積三角形はほとんどなく、したがって 2 個、3 個、または 4 個の低面積三角形によって形成される閉路の数は線形以下の数だけであることを証明します。これらの閉路に属するすべての点を削除します。
• 高い内周の3 均一ハイパーグラフに三角形除去補題を適用して、残りの点には、小面積の三角形を形成しない点のサブセットが高確率で含まれることを示します。${\displaystyle n}$

これらの構築によって生じる面積は、漸近的に増加します。^[5] 証明は非ランダム化することができ、この三角形の面積を持つ配置を構築するための多項式時間アルゴリズムにつながります。^[6]$${\displaystyle \Delta (n)=\Omega \left({\frac {\log n}{n^{2}}}\right).}$$

単位正方形内の点の集合はどれも、最大でに反比例する面積の三角形を形成します。これを確認する 1 つの方法は、与えられた点集合の凸包を三角形に分割し、三角形分割された三角形の中で最小の三角形を選択することです。もう 1 つの方法は、点を-座標で並べ替え、この順序で-座標が最も近い3 つの連続する点を選択することです。1951 年に発表されたハイルブロンの三角形問題に関する最初の論文で、クラウス・ロスはのより強い上限を次の形式で証明しました^[1]。現在までに知られている最良の上限は、コムロス、ピンツ、セメレディ (1981) によって証明された、 ある定数に対する 形式です 。 ^[7]${\displaystyle n}$${\displaystyle n}$${\displaystyle S}$${\displaystyle x}$${\displaystyle x}$${\displaystyle \Delta (n)}$ $${\displaystyle \Delta (n)=O\left({\frac {1}{n{\sqrt {\log \log n}}}}\right).}$$$${\displaystyle \Delta (n)\leq {\frac {\exp {\left(c{\sqrt {\log n}}\right)}}{n^{8/7}}},}$$${\displaystyle c}$

に等しい新たな上限がCohen、Pohoata、Zakharov（2023）によって証明された。^{[8] [9]}${\displaystyle n^{-{\frac {8}{7}}-{\frac {1}{2000}}}}$

ゴールドバーグ (1972) は、 16 までの点について、正方形内の点の最適な配置を調査しました。^[2]ゴールドバーグの構成は、最大 6 点が正方形の境界上にあり、正多角形の頂点のアフィン変換を形成するように配置されます。の値がこれより大きい場合、コメラスとイェブラ (2002) はゴールドバーグの境界を改良し、これらの値では解に正方形の内部の点が含まれます。^[3]これらの構成は、最大 7 点に対して最適であることが証明されています。証明では、コンピューター検索を使用して、点の可能な配置の構成空間を226 の異なるサブ問題に分割し、非線形計画法を使用して、そのうち 225 のケースで、最適な配置が既知の境界ほど良くないことを示しました。最終的な最適解を含む残りのケースでは、記号計算技術を使用してその最適性が証明されました。^[4]${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$

以下は、シミュレーテッドアニーリング法によって発見された、単位正方形内の7～12点の最もよく知られている解である。^[3] 7点の配置が最適であることが知られている。^[4]

• 
  正方形に 7 つの点があり、8 つの極小三角形すべてが塗りつぶされている( )${\displaystyle A\approx 0.0839}$
• 
  正方形内の8点、12個の極小三角形のうち5個が塗りつぶされている^[d] （）${\displaystyle A\approx 0.0724}$
• 
  正方形内の9つの点、11個の極小三角形のうち6個が塗りつぶされている^[d] （）${\displaystyle A\approx 0.0549}$
• 
  正方形に10点、16個の極小三角形のうち3個が塗りつぶされている^[d] （）${\displaystyle A\approx 0.0465}$
• 
  正方形内の11点、28個の極小三角形のうち8個が塗りつぶされている^[d] （）${\displaystyle A\approx 0.0370}$
• 
  正方形内の12点、20個の極小三角形のうち3個が塗りつぶされている^[d] （）${\displaystyle A\approx 0.0326}$

与えられた形状の最適な配置を探す代わりに、与えられた点の数に最適な形状を探すこともできます。面積が 1 の凸形状のうち、正六角形は を最大化します。この形状では、 6 つの点が六角形の頂点に最適に配置されます。^[10]面積が最大化される単位面積の凸形状はを持ちます。^[11]${\displaystyle D}$${\displaystyle \Delta _{D}(6)}$${\displaystyle \Delta _{D}(6)={\tfrac {1}{6}}}$${\displaystyle \Delta _{D}(7)}$${\displaystyle \Delta _{D}(7)={\tfrac {1}{9}}}$

この問題には多くのバリエーションがあり、一様にランダムな点の集合の場合もその一つで、コルモゴロフ複雑性またはポアソン近似に基づく議論では、最小面積の期待値は点の数の3乗に反比例することが示されています。 ^{[12] [13]高次元}単体の体積に関するバリエーションも研究されています。^{[14] [15] [16]}

単体を考慮する代わりに、別の高次元バージョンでは、別のパラメータを追加し、${\displaystyle k}$任意の点のサブセットの凸包の最小体積を最大化する単位超立方体内の点の配置を求めます。これらのサブセットは単体を形成しますが、の値がに対して大きい場合、より複雑な形状を形成する可能性があります。が に対して十分に大きい場合、ランダムに配置された点セットは最小の-点凸包体積を持ちます。これより優れた境界は不可能です。任意の配置には、座標順にいくつかの連続する点を選択することで得られる体積の点が含まれます。この結果は、範囲検索データ構造に応用できます。^[17]${\displaystyle n}$${\displaystyle k}$${\displaystyle k=d+1}$${\displaystyle k}$${\displaystyle d}$${\displaystyle k}$${\displaystyle \log n}$${\displaystyle k}$${\displaystyle \Omega (k/n)}$${\displaystyle k}$${\displaystyle O(k/n)}$${\displaystyle k}$

• ダンツァー集合、大きな面積の空三角形を避ける点の集合

• ワイスタイン、エリック W.、「ハイルブロンの三角形問題」、MathWorld
• エーリッヒ・フリードマン著の「エーリッヒのパッキングセンター」には、正方形、円、正三角形、および形状は変化するが面積は一定である凸領域に対する、小さな値のハイルブロン問題に対する最もよく知られた解法が含まれています。${\displaystyle n}$