Kセット（ジオメトリ）

離散幾何学において、ユークリッド平面上の有限点集合の -集合は、直線によって残りの点から厳密に分離できる の要素の部分集合です。より一般的には、高次元のユークリッド空間では、有限点集合の -集合は、超平面によって残りの点から分離できる要素の部分集合です。特に、(ここでは のサイズ) のとき、 -集合を の残りの部分から分離する直線または超平面は、半分割線または半分割平面です。 ${\displaystyle k}$${\displaystyle S}$${\displaystyle k}$${\displaystyle S}$${\displaystyle k}$${\displaystyle k}$${\displaystyle k=n/2}$${\displaystyle n}$${\displaystyle S}$${\displaystyle k}$${\displaystyle S}$

平面上の点の集合の -集合は、射影双対性によって直線の配置の -レベルに関連付けられます。平面上の直線の配置の -レベルとは、直線の 1 つ上にあり、その下にちょうど 本の直線がある点で構成される曲線です。離散幾何学者や計算幾何学者は、より一般的な種類の曲線や曲面の配置のレベルも研究してきました。^[1]${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$${\displaystyle n}$${\displaystyle k}$

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

平面上の点の集合における半直線の最大数はいくつですか?${\displaystyle n}$

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

幾何学アルゴリズムの解析において、平面点集合の集合の数^[2]またはそれと同等の平面線配置のレベルの数を限定することは重要であり、この問題は最初にLovász ^[3]とErdősら^[4]によって研究されました。この問題の最もよく知られている上限は であり、 Tamal Dey ^[5]がAjtai、Chvátal、Newborn、およびSzemerédiの交差数不等式を使用して示しました。しかし、最もよく知られている下限は Dey の上限からは程遠く、Tóth ^[6]によって示されているように、ある定数 に対するものです。${\displaystyle k}$${\displaystyle k}$${\displaystyle O(nk^{1/3})}$${\textstyle \Omega (nc^{\sqrt {\log k}})}$${\displaystyle c}$

3次元では、既知の最良の上限は であり、既知の最良の下限は です。^{[7] 3次元で}凸位置 にある点、つまり何らかの凸多面体の頂点の場合、-集合の数は であり 、これは次ボロノイ図の複雑性を制限しようとする議論から導かれます。 ^[8]${\displaystyle O(nk^{3/2})}$${\textstyle \Omega (nkc^{\sqrt {\log k}})}$${\displaystyle k}$${\displaystyle \Theta {\bigl (}(nk)k{\bigr )}}$${\displaystyle k}$

（半割り線）の場合、 の2点を通り残りの点を二等分する組み合わせ的に異なる直線の最大数は、 ${\displaystyle k=n/2}$${\displaystyle S}$${\displaystyle k=1,2,\dots }$

-集合の数にも上限が証明されており、-集合はある に対して -集合となる。2次元では、-集合の最大数はちょうど である^{[9] が}、次元では上限は である^[10]。${\displaystyle \leq k}$${\displaystyle \leq k}$${\displaystyle j}$${\displaystyle j\leq k}$${\displaystyle \leq k}$${\displaystyle nk}$${\displaystyle d}$${\displaystyle O(n^{\lfloor d/2\rfloor }k^{\lceil d/2\rceil })}$

Edelsbrunner と Welzl ^[11]は、最初に入力点集合のすべての -集合を構築する問題、または二重に配置の -レベルを構築する問題を研究しました。彼らのアルゴリズムの -レベル バージョンは、レベルを左から右の順序で構築する平面スイープアルゴリズムとして考えることができます。点集合の -集合の観点から見ると、彼らのアルゴリズムは、分離線の両側の点に対して動的な凸包を維持し、これら 2 つの包の二重接線を繰り返し見つけ、2 つの接点のそれぞれを反対側の包に移動します。Chan ^{[12] は}、この問題に関するその後の結果を調査し、-レベルの複雑さに関する Dey の境界に比例する時間で解決できることを示しました。 ${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$${\displaystyle O(nk^{1/3})}$${\displaystyle k}$

アガルワルとマトウシェクは、近似レベル、つまり、ある小さな近似パラメータに対して-レベルと-レベルの間を通る曲線を効率的に構築するためのアルゴリズムについて説明しています。彼らは、 のみに依存し、や には依存しない多数の線分で構成されるそのような近似が見つかることを示しています。^[13]${\displaystyle (k-\delta )}$${\displaystyle (k+\delta )}$${\displaystyle \delta}$${\displaystyle n/\delta }$${\displaystyle n}$${\displaystyle k}$

平面レベルの問題は、マトロイドのパラメトリック最適化の問題に一般化できます。つまり、各要素がパラメータ の線形関数によって重み付けされているマトロイドが与えられ、 の各可能な値に対してマトロイドの最小重み基底を見つけなければなりません。重み関数を平面上の線としてグラフ化すると、これらの線の配置の -レベルは、一様マトロイドの最適基底における最大要素の重みの関数としてグラフ化されます。また、Dey は、 -レベルの複雑性に関する彼の境界が、要素 およびランク を持つ任意のマトロイドの異なる最適基底の数を数えることに一般化できることを示しました。 ${\displaystyle k}$${\displaystyle \lambda}$${\displaystyle \lambda}$${\displaystyle k}$${\displaystyle \lambda}$${\displaystyle O(nk^{1/3})}$${\displaystyle k}$${\displaystyle n}$${\displaystyle k}$

例えば、辺と頂点を持つグラフで形成される異なる最小全域木の数を数える場合にも、同じ上限が成り立ちます。この場合、辺の重みはパラメータに応じて線形に変化します。このパラメトリック最小全域木問題は、さまざまな著者によって研究されており、他の2基準全域木最適化問題を解決するために使用できます。^[14]${\displaystyle O(nk^{1/3})}$${\displaystyle n}$${\displaystyle k}$${\displaystyle \lambda}$

しかし、パラメトリック最小全域木問題に対する最もよく知られている下限は であり、 -集合問題に対する下限よりも弱い下限である。 ^[15]より一般的なマトロイドの場合、デイの上限には一致する下限がある。^[16]${\displaystyle \Omega (n\log k)}$${\displaystyle k}$${\displaystyle O(nk^{1/3})}$

• 半減線とkセット、ジェフ・エリクソン
• 未解決問題プロジェクト、問題 7: k セット