最小円問題

最小円問題（最小被覆円問題、境界円問題、最小境界円問題、最小外接円問題とも呼ばれる）は、ユークリッド平面上の与えられた点の集合をすべて含む最小の円を計算する計算幾何学の問題である。n次元空間における対応する問題である最小境界球面問題は、与えられた点の集合をすべて含む最小のn球面を計算することである。 ^[1]最小円問題は、 1857年にイギリスの数学者ジェームズ・ジョセフ・シルベスターによって最初に提唱された。^[2]

平面上の最小円問題は、施設配置問題（1中心問題）の一例であり、多数の顧客にサービスを提供できるように新しい施設の場所を選択し、顧客が新しい施設に到達するために移動しなければならない最長距離を最小化する必要がある。^[3]平面上の最小円問題と、境界次元の任意の高次元空間における最小境界球問題は、どちらも最悪の場合でも 線形時間で解くことができる。

この問題に対する幾何学的アプローチのほとんどは、最小円の境界上にある点を探すもので、次の単純な事実に基づいています。

• 最小被覆円は一意です。
• 集合Sの最小被覆円は、円の境界上にあるS内の最大 3 つの点によって決定できます。最小被覆円が 2 つの点のみによって決定される場合、その 2 つの点を結ぶ線分は最小円の直径でなければなりません。最小被覆円が 3 つの点によって決定される場合、その 3 つの点からなる三角形は鈍角ではありません。

ニムロド・メギドが示したように、^[5]最小の包囲円は線形時間で見つけることができ、同じ線形時間境界は任意の定数次元のユークリッド空間内の最小の包囲球にも適用されます。彼の論文では、以前のアルゴリズムとアルゴリズムの概要も簡単に説明しています。^[6]そうすることで、メギドはシャモスとホーイの予想、つまり最小円問題の解はせいぜい で計算可能であるという予想が誤りであることを実証しました。^[7]${\displaystyle O(n^{3})}$${\displaystyle O(n\log n)}$${\displaystyle \Omega (n\log n)}$

エモ・ウェルツル^[8]は、ライムント・ザイデルの線形計画アルゴリズムに基づいて、期待時間で実行される最小被覆円問題のための単純なランダム化アルゴリズムを提案した。 ${\displaystyle O(n)}$

その後、最小円問題は、線形計画法に基づくウェルツルのアルゴリズムなどのアルゴリズムで解くことができるLP 型問題の一般的なクラスに含められました。このクラスに属することの結果として、ザイデル法では階乗であった時間境界の定数因子の次元への依存性が、準指数にまで低減できることが示されました。^[6]ウェルツルのミニディスクアルゴリズムは、ユークリッド距離の二乗を含む ブレグマンダイバージェンス^[9] を処理できるように拡張されました。${\displaystyle O(n)}$

Megiddoのアルゴリズム^[10]は、不要な点を削除することで問題のサイズを縮小する、プルーンアンドサーチと呼ばれる手法に基づいています。これにより、再帰が実現され、 が得られます。 ${\textstyle {\frac {n}{16}}}$${\displaystyle t(n)\leq t\left({\frac {15n}{16}}\right)+cn}$${\displaystyle t(n)=16cn}$

このアルゴリズムはかなり複雑で、大きな乗法定数にそれが反映されています。この削減では、求める囲み円の中心が特定の線上に制約されている同様の問題を 2 回解く必要があります。サブ問題の解は、制約のない問題の解であるか、制約のない解の中心が配置されている半平面を決定するために使用されます。

破棄される点は次のようにして見つけられます: 点P i_は、線p _jをその二等分線として定義するペアに並べられます。二等分線の中央平均値p _{m が}、方向の順 (二等分線p ₁によって決定される同じ半平面に向けられる) で求められ、各ペアで 1 つの二等分線の方向が最大でp _mで、もう 1 つの二等分線の方向が少なくともp _{m に}なるように二等分線のペアが作成されます (方向p ₁は、必要に応じて-または +と見なすことができます)。k番目のペアの二等分線の交点をQ _kとします。 ${\textstyle {\frac {n}{16}}}$${\textstyle {\frac {n}{2}}}$${\displaystyle \infty}$${\displaystyle \infty}$

p ₁方向の直線q は、交点Q _{x を}通るように配置され、直線 (中央位置) によって定義される各半平面に交点があるようになります。囲み問題の制約バージョンは、中心が位置する半平面を決定する直線 q' 上で実行されます。p _m方向の直線q ′ は、解を含まない半平面の各半分に交点があるように、交点Q _{x' を}通るように配置されます。囲み問題の制約バージョンは、直線q ′ 上で実行され、直線qとともに中心が位置する象限が決定されます。解を含む半平面に含まれない象限内の点Q _{k を}検討します。Q _kを定義するペアの二等分線の 1 つには、二等分線を定義する点P _iのどちらが、囲む円の中心を含む象限内の各点により近いかを保証する方向があります。この点は破棄できます。 ${\textstyle {\frac {n}{8}}}$${\textstyle {\frac {n}{16}}}$

制約付きバージョンのアルゴリズムもプルーンと探索の手法で解けるが、再帰につながるポイント を削除することで問題のサイズを縮小する。${\textstyle {\frac {n}{4}}}$

${\displaystyle t(n)\leq t\left({\frac {3n}{4}}\right)+cn}$

与える。 ${\displaystyle t(n)=4cn}$

破棄される点は次のようにして見つけられます。点P i_はペアに並べられます。各ペアについて、その二等分線と制約線qとの交点Q _jが見つかります (この交点が存在しない場合は、ペアからすぐに 1 つの点を削除できます)。線q上の点Q _jの中央値Mが見つかり、Mから始まるqの半直線のどれが 制約問題の解を含むかをO ( n ) 時間で決定します。もう半分からの点Q _{jを検討します。Q j を}定義する点P _iのどれが、制約問題の解の囲み円の中心を含む半直線の各点に近いかがわかっています。この点は破棄できます。 ${\textstyle {\frac {n}{4}}}$

制約のない解が存在する半平面は、制約のある円の解の境界上の点P _iによって決定できます。(各半平面の円上の最初と最後の点で十分です。中心が凸包に属している場合は制約のない解であり、そうでない場合は最も近いエッジへの方向によって制約のない解の半平面が決定されます。)

アルゴリズムは再帰的です。

初期入力は点の集合Pです。アルゴリズムはPからランダムかつ均一に1 つの点p を選択し、 P - { p }、つまりpを除くP内の他のすべての点を含む最小の円を再帰的に見つけます。返された円がpも囲んでいる場合、それはP全体の最小の円であり、返されます。

それ以外の場合、点p は結果の円の境界上にある必要があります。これは再帰的ですが、境界上にあることがわかっている点の 集合Rが追加パラメータとして使用されます。

Pが空になると再帰は終了し、 R内の点から解が見つかります。点が 0 または 1 の場合、解は自明です。点が 2 の場合、最小円の中心は 2 点間の中点にあり、点が 3 の場合、円は点で表された三角形の外接円です。(3 次元では、点が 4 の場合、四面体の外接球面を計算する必要があります。)

P内の残りの点はRによって表される円内になければならないため、 R のサイズが 3 (2D の場合、または 3D の場合は 4) のときにも再帰は終了することがあります。

アルゴリズムウェルツルは[8]
    入力:平面上の点の有限集合PとR | R |≤3。
    出力:境界上でPとRを囲む最小の円。

     Pが空または| R | = 3の場合、
         trivial( R )
    を返す。P内のpを選択する(ランダムかつ均一に) 
    D := welzl( P − { p }, R )
     pがDに含まれる場合 はDを返す 
         

    welzl( P − { p }, R ∪ { p })
を返す

Welzl の論文では、各再帰でpを独立してランダムに選択するのではなく、開始時に入力をランダムに並べ替えるだけで十分であると述べています。

また、円の外側にあることが判明した点が後でより早く考慮されるように点を動的に並べ替えることによってパフォーマンスが向上するとも述べられていますが、これにはPを「グローバル」として保存するためにアルゴリズムの構造を変更することが必要になります。

最小円問題が線形時間で解けることを示すメギドの結果が出る前に、より複雑なアルゴリズムがいくつか文献に登場しました。単純なアルゴリズムでは、すべての点のペアとトリプルによって決定される円をテストすることで、O(n4) の時間で問題を解決^します 。

• ChrystalとPeirceのアルゴリズムは、外接円の境界上に2つの点を維持し、最適な円が見つかるまで境界点のペアを置き換えながら円を繰り返し縮小する局所最適化戦略を適用します。ChakrabortyとChaudhuri ^[11]は、適切な初期円とその円上の境界点のペアを選択するための線形時間法を提案しています。アルゴリズムの各ステップには、2つの境界点の1つとして凸包の新しい頂点が含まれるため、包にh個の頂点がある場合、この方法はO( nh )の時間で実行するように実装できます。
• Elzinga と Hearn ^[12]は、点のサブセットをカバーする円を維持するアルゴリズムについて説明しました。各ステップで、現在の球でカバーされていない点を使用して、見つかった点を含む新しい点のサブセットをカバーするより大きな球を見つけます。最悪の場合の実行時間は O( h ³ n ) ですが、著者らは実験では線形時間で実行されたと報告しています。この方法の複雑さは Drezner と Shelah によって分析されています。^[13] FortranとC の両方のコードは Hearn、Vijay、Nickel (1995) から入手できます。^[14]
• 最小球面問題は、凸二次目的関数を持つ線形制約のシステムによって定義される二次計画法^{[1]として定式化できます。したがって、任意の実行可能方向アルゴリズムでこの問題を解くことができます。 [15]} Hearn と Vijay ^{[16] は}、Jacobsen が選択した実行可能方向アプローチが Chrystal–Peirce アルゴリズムと同等であることを証明しました。
• この二次計画法の双対も明示的に定式化することができる。^[17]ローソンのアルゴリズム^[18]は、このようにして原始双対アルゴリズムとして記述することができる。^[16]
• ShamosとHoey ^[7]は、最小の囲み円の中心は入力点集合の最も遠いボロノイ図の頂点でなければならないという観察に基づいて、この問題に対するO( n  log  n )時間のアルゴリズムを提案した。

最小被覆円問題の重み付きバージョンは、ユークリッド空間内の各点の集合を入力として受け取り、各点に重みが付けられます。目標は、任意の点への最大重み付き距離（つまり、距離に対応する重みを乗じた値）を最小化する単一の点を見つけることです。元の（重みなしの）最小被覆円問題は、すべての重みが 1 に等しい場合に対応します。重みなしの問題と同様に、重み付き問題は、境界次元の線形計画アルゴリズムに密接に関連するアプローチを使用して、境界次元の任意の空間で線形時間で解くことができますが、より遅いアルゴリズムも文献でよく使用されています。^{[16] [19] [20]}

有限点集合の最小の包接球は、カルタン・アダマール多様体を含むリーマン幾何学において研究されてきた。^[21]

• 境界球
• 1センター問題
• 外接円
• 最も近い文字列
• ユングの定理

• ベルント・ガートナーの最小の囲みボールコード
• CGAL計算幾何学アルゴリズム ライブラリ(CGAL)のMin_sphere_of_spheresパッケージ
• Miniball は、低次元および中程度に高い次元の最小包囲球問題に対するアルゴリズムのオープンソース実装です。