ラインの配置

幾何学において、直線の配置とは、ユークリッド平面を有限の直線の集合で分割したものである。配置は、有界凸多角形と無界凸多角形 (配置のセル)、線分と光線 (配置の辺)、および 2 つ以上の直線が交差する点 (配置の頂点) で構成される。ユークリッド平面ではなく射影平面で考えると、 2 本の直線はすべて交差し、配置は有限の点の集合に対する射影双対となる。直線の配置は双曲平面でも考えられ、直線と同様の位相特性を持つ曲線である擬似直線に一般化されている。配置に関する最初の研究は、ヤコブ・シュタイナーによる 1826 年の論文とされている。

配置は、各頂点で最大 2 本の線が交差する場合に単純であり、すべてのセルが三角形(射影平面の部分集合としての境界のないセルを含む) である場合に単体的であるといわれます。単体的配置には 3 つの既知の無限族があり、既知の族に当てはまらない散発的な単体的配置も多数あります。配置は、無限だが局所的に有限な線体系についても検討されています。平行線の特定の無限配置は単体的配置を形成することができ、非周期的なペンローズ タイルを作成する方法の 1 つは、 5 つの平行部分集合を形成する線配置の双対 グラフを見つけることです。

与えられた数の線による配置におけるセル、辺、頂点の最大数は、線の数の2 次関数です。これらの最大値は、単純な配置によって達成されます。配置のその他の特徴の複雑さは、離散幾何学で研究されてきました。これには、ゾーン (単一の線に接するセル) やレベル (下を通過する線が与えられた数の多角形の鎖) が含まれます。ロバーツの三角形定理とコボンの三角形問題は、それぞれユークリッド配置における三角形セルの最小数と最大数に関するものです。

計算幾何学のアルゴリズムは、配置の特徴を、特徴の数に比例した時間と、線の数に比例した空間で構築することで知られています。また、研究者は、配置のより小さな部分を構築するための効率的なアルゴリズムや、配置の頂点と辺上の最短経路問題などの問題に対する効率的なアルゴリズムを研究してきました。

非公式の思考実験として、無限の紙を有限の線に沿って切ることを考えてみましょう。これらの切断により、紙は凸多角形に分割されます。それらの辺は、2 本の切断線が交差する点を頂点とする1 次元の線分または放射線になります。これは、平面上の点を各線のどちら側にあるかによって分類することで数学的に形式化できます。各線は、点ごとに 3 つの可能性を生み出します。点は、線の両側にある 2 つの開いた半平面のいずれかにあるか、線上にあるかです。2 つの点は、すべての線に関して同じ分類である場合に同等であると考えられます。これは同値関係であり、同値類は同等な点のサブセットです。これらのサブセットは、平面を次の 3 つのタイプの形状に細分化します。^[1]

1. 配列のセルまたはチャンバーは、どの線にも属さない2次元領域です。これらは、境界のある凸多角形または境界のない凸領域の内部を形成します。これらは、線上のすべての点を削除した後に残る点の接続されたコンポーネントです。 ^[1]
2. 配置のエッジまたはパネルは、 1 本の線に属する 1 次元の領域です。これらは、各線が他の線との交差点によって分割される開いた線分と開いた無限光線です。つまり、1 本の線が他のすべての線によって切断された場合、これらは切断されていない点の接続されたコンポーネントです。^[1]
3. 配置の頂点は、2本以上の線が交差する孤立した点である。^[1]

セルの境界は、それに接する辺のシステムであり、辺の境界は、それに接する頂点の集合です（光線の場合は 1 つの頂点、線分の場合は 2 つの頂点）。この境界演算子によってリンクされた 3 つのタイプのオブジェクトのシステムは、平面を覆うセル複合体を形成します。関連するセル複合体内のオブジェクト間に 1 対 1 の境界保存対応がある場合、2 つの配置は同型または組み合わせ的に同等であると言われます。^[1]

同じ点の分類、および同値類の同じ形状は、平面のすべての境界付きサブセットが有限個の線によって交差される配置として定義される、無限だが局所的に有限な配置にも使用できます。 ^[2]この場合、境界のないセルには無限の数の辺がある場合があります。^[3]

配置内の頂点、辺、セルの最大数を数えるのは簡単です。これらはすべて行数の 2 乗です。

• 直線の配置には、交差する直線の組ごとに 1 つずつ、最大で頂点 (三角数) があります。この最大値は、2 本の直線が他のすべての直線とは交わらない頂点で交差する単純な配置で達成されます。一部の直線が平行である場合、または一部の頂点が 2 本以上の直線と交差している場合は、頂点の数は少なくなります。^[4]${\displaystyle n}$${\displaystyle n(n-1)/2}$
• 必要に応じて、軸に平行な線を避けるために、アレンジメントを回転することができます。このステップの後、アレンジメントのエッジを形成する各光線は、その端点から上または下のいずれかに伸びます。水平になることはできません。下向きの光線は、線ごとに 1 つあり、これらの光線は、下方向に制限されていないアレンジメントのセルを分離します。残りのセルはすべて、一意の最下部の頂点を持ちます (これも、軸に平行な線がないため)。各線のペアについて、2 つの線が下部の頂点で交わるセルは 1 つだけであるため、下方向に制限されたセルの数は、線のペアの数、最大になります。制限されていないセルと制限されたセルを追加すると、アレンジメント内のセルの合計数は最大になります。^[5]これらは、怠け者の数列の数です。^[6]${\displaystyle n}$${\displaystyle n+1}$${\displaystyle n(n-1)/2}$${\displaystyle n(n+1)/2+1}$
• 配置の辺の数は最大 であり、これは${\displaystyle n^{2}}$オイラー特性を使用して頂点とセルの数から計算するか、各線が他の線によって最大 の辺に分割されることを観察することによって確認できます。単純な配置にはちょうど の辺があります。^[5]${\displaystyle n}$${\displaystyle n-1}$${\displaystyle n^{2}}$

より複雑な機能は、「ゾーン」、「レベル」、「多数の面」などと呼ばれます。

• 直線配置における直線のゾーンは、に属する辺を持つセルの集合である。ゾーン定理によれば、単一ゾーンのセルの辺の総数は線形である。より正確には、直線の片側に属するセルの辺の総数は最大で であり、^{[7] の}両側に属するセルの辺の総数は最大で である。^[8]より一般的には、任意の凸曲線と交差する直線配置のセル全体の複雑度は であり、ここで は逆アッカーマン関数を表し、ダベンポート・シンツェル列 を使用して示すことができる。^[9]配置内のセル複雑度の二乗和は であり、これはすべての直線のゾーンを合計することによって示すことができる。^[10]${\displaystyle \ell}$${\displaystyle \ell}$${\displaystyle \ell}$${\displaystyle 5n-1}$${\displaystyle \ell}$${\displaystyle \lfloor 9.5n\rfloor -1}$ ${\displaystyle O(n\alpha (n))}$${\displaystyle \alpha}$${\displaystyle O(n^{2})}$
• 配置の-レベルは、その真下に他の線が 1 本だけあるエッジによって形成される多角形の鎖です。-レベルは、配置のうち - レベルの下にある部分です。 -レベルの複雑さの上限と下限を一致させることは、離散幾何学における主要な未解決問題です。知られている最良の上限はで、知られている最良の下限は です。^[11]対照的に、- レベルの最大の複雑さはであることが知られています。^[12] - レベルは、配置における単調なパスの特殊なケースです。つまり、1 つの点で任意の垂直線と交差するエッジのシーケンスです。ただし、単調なパスは- レベルよりもはるかに複雑である可能性があります。これらの配置には、パスの方向が変わる点の数が である配置と単調なパスが存在します。[ ^13]${\displaystyle k}$${\displaystyle k}$${\displaystyle \leq k}$${\displaystyle k}$${\displaystyle k}$${\displaystyle O(nk^{1/3})}$${\displaystyle n2^{\Omega ({\sqrt {\log k}})}}$${\displaystyle \leq k}$${\displaystyle \Theta (nk)}$${\displaystyle k}$${\displaystyle k}$${\displaystyle n^{2-o(1)}}$
• 配列内の単一のセルはすべての線で囲まれているかもしれませんが、一般に、異なるセルがすべて線で囲まれることは不可能です。むしろ、セルの合計複雑度は最大で であり、^[14]平面上の点と線の交差に関するセメレディ・トロッターの定理で発生する制限とほぼ同じです。この簡単な証明は、交差数不等式から得られます。^[15]セルに合計 のエッジがある場合、ノード (セルごとに 1 つ) とエッジ (同じ線上の連続するセルのペアごとに 1 つ) を持つグラフを形成できます。このグラフのエッジは、端点に対応するセル内で交差しない曲線として描画でき、その後、配列の線に沿って描画されます。したがって、この描画には交差があります。ただし、交差数不等式により、交差があります。両方の制限を満たすには、である必要があります。[ ^16]${\displaystyle n}$${\displaystyle m}$${\displaystyle n}$${\displaystyle m}$${\displaystyle \Theta (m^{2/3}n^{2/3}+n)}$${\displaystyle m}$${\displaystyle x+n}$${\displaystyle m}$${\displaystyle x}$${\displaystyle O(n^{2})}$${\displaystyle \Omega (x^{3}/m^{2})}$${\displaystyle x}$${\displaystyle O(m^{2/3}n^{2/3})}$

射影平面における線の配置を調べるのは、すべての直線のペアに交差点があるため便利です。 ^[17]射影平面の線は平面を2つの異なる辺に分割しないため、線の配置は線の辺を使用して定義できません。^[18]それでも、配置のセ​​ルはどの線にも属さない点の接続成分、辺は単一の線に属する点の集合の接続成分、頂点は2本以上の線が交差する点として定義できます。射影平面における線の配置は、線の両端にある2本のユークリッド光線が、その線上の左端と右端の頂点を接続する射影平面の1本の辺に置き換えられ、無限遠のユークリッドセルのペアが射影平面で射影線が無限遠で交差する単一のセルに置き換えられる点で、ユークリッドの配置と異なります。^[19]

射影双対性のため、平面上の点の組み合わせ的性質に関する多くの主張は、直線の配置に関する同等の双対形式でより容易に理解できる。例えば、平面上の任意の非共線的点集合にはちょうど 2 点を含む通常の直線が存在するというシルベスター・ガライの定理は、射影双対性の下では、1 つ以上の頂点を持つ有限本の直線の射影配置には通常の点、つまり 2 本の直線だけが交差する頂点が存在するという主張に変換される。シルベスター・ガライの定理の最も古い証明は、1940 年にエーバーハルト・メルヒオールによってなされたもので、オイラー標数を使用してそのような頂点が必ず存在することを示していた。^[20]

射影平面上の直線の配置は、その配置のセルすべてがちょうど3つの辺で囲まれている場合、単体的であると言われる。単体的配置はメルヒオールによって初めて研究された。 ^[21]単体的直線配置には3つの無限族が知られている。

1. 一つの点を通る線と、同じ点を通らない一本の線で構成された鉛筆に近いもの。${\displaystyle n-1}$
2. 正多角形の辺とその対称軸によって形成される線の族、および
3. 正多角形の辺と対称軸、および無限遠の直線。

さらに、既知の無限族に当てはまらない散発的な単体配置の例は他にも多数ある。 ^[22]ブランコ・グリュンバウムが書いている ように、単体配置は「組合せ幾何学とその応用の多くの文脈で例や反例として現れる」。^{[23]たとえば、単体配置は、}微分方程式の次数と方程式が持つ不変直線の数との関係に関する予想に対する反例となる。[ ^24]ディラック・モツキン予想（任意の -直線配置には少なくとも通常の点があるという予想）に対する既知の反例は 2つとも単体である。^[25]${\displaystyle n}$${\displaystyle n/2}$

線状配置の双対グラフには、セルごとに 1 つのノードと、配置のエッジを共有する任意の 2 つのセルをリンクする 1 つのエッジがあります。これらのグラフは部分立方体であり、グラフの距離がラベル間のハミング距離に等しくなるように、ノードをビットベクトルでラベル付けできるグラフです。線状配置の場合、ラベル付けの各座標は、1 つの線の片側のノードに 0 を割り当て、反対側のノードに 1 を割り当てます。^{[26]単体配置の双対グラフは、}単純なゾノヘドラのグラフと同型の3 正則部分立方体の無限の族を構築するために使用されています。^[27]

必ずしも単体ではない配置における三角形セルの極値の数を調べることも興味深い。射影平面内のどの配置も、少なくとも 個の三角形を持つ必要がある。三角形だけを持つすべての配置は単純でなければならない。^[28]射影配置ではなくユークリッド配置の場合、ロバーツの三角形定理より、三角形の最小数は 個である。^[29]単純配置における三角形面の最大可能数は、上限が 個、下限が個であることが知られている。下限は、正多角形の対角線の特定の部分集合によって達成される。^[30]単純である必要がない射影配置の場合、すべての に対して三角形を持つ配置が存在し、 を持つすべての配置には最大で個の三角形が含まれる。^[31]密接に関連するKobon の三角形問題は、ユークリッド平面内の配置における重なり合わない有限三角形の最大数を求める問題であり、射影平面で三角形を形成する可能性のある無限面はカウントされない。繰り返しますが、配置は単純である必要はありません。のすべての値ではないいくつかの値に対して、三角形の配置が存在します。^[32]${\displaystyle n}$${\displaystyle n}$${\displaystyle n-2}$${\displaystyle n(n-1)/3}$${\displaystyle n(n-3)/3}$${\displaystyle 2n}$${\displaystyle n(n-1)/3+4}$${\displaystyle n\geq 4}$${\displaystyle n\geq 6}$${\displaystyle 7n(n-1)/18+1/3}$${\displaystyle n}$${\displaystyle n(n-2)/3}$

単純な直線配置の双対グラフは、幾何学的には、配置の頂点ごとに1つずつ、その頂点で交わる直線に垂直な辺を持つ菱形の集合として表現できる。これらの菱形は、有限本の直線の配置の場合は凸多角形のタイリングを形成するために結合されるか、無限本の直線による局所有限配置の場合は平面全体のタイリングを形成する。この構成は、この手法を使用したルドルフ・クレーの1938年の出版物にちなんで、クレー図と呼ばれることもある。ただし、すべての菱形のタイリングがこのように直線から作られるわけではない。^[33]

1981年の論文で、NG de Bruijn は、等間隔の平行線の集合からなる線の配置というこの構成の特殊なケースを調査した。2 つの直交する平行線族の場合、この構成は平面の正方形のタイリングを与え、互いに 120 度の角度にある 3 つの線族 (それ自体が三六角形のタイリングを形成) の場合、これは菱形のタイリングを生成する。しかし、より多くの線族の場合、この構成は非周期的なタイリングを生成する。特に、互いに等しい角度にある 5 つの線族 (または、de Bruijn がこの配置をペンタグリッドと呼ぶ) の場合、ペンローズのタイリングの菱形バージョンを含むタイリングの族を生成する。^[34]${\displaystyle k}$

平行線のセットから形成される無限単体配置も 3 つ存在します。テトラキス正方形タイリングは、4 つの平行なファミリーを持つマルチグリッドに似た周期的なタイリングを形成する線の無限配置ですが、ファミリーのうち 2 つは他の 2 つよりも間隔が広く、配置は単純ではなく単体です。その双対は切頂正方形タイリングです。同様に、三角形タイリングは 3 つの平行なファミリーを持つ無限単体線配置で、その双対は六角形タイリングです。また、二等分六角形タイリングは、6 つの平行なファミリーと 2 つの線間隔を持つ無限単体線配置で、大菱形三六角形タイリングの双対です。これら 3 つの例は、ユークリッド平面の 3 つのアフィン反射群、つまりこれらの配置の各線をまたぐ反射に基づく対称システムから来ています。 ^[35]

配置を構築するということは、配置内の線のリストを入力として与えられ、配置の頂点、辺、セルの表現と、これらのオブジェクト間の隣接関係を計算することを意味します。たとえば、これらの特徴は、二重に接続された辺のリストとして表すことができます。配置は、以前に追加された線の配置に一度に 1 行ずつ追加する増分アルゴリズムによって効率的に構築できます。新しい線はそれぞれ、ゾーンのサイズに比例した時間で追加でき、ゾーン定理によって線形になります。これにより、合計構築時間は になります。[ ^7]${\displaystyle O(n^{2})}$このアルゴリズムのメモリ要件も です。代わりに、トポロジカル スイープと呼ばれるアルゴリズム手法を使用して、時間と空間で配置の特徴を一度に格納せずに報告することができます。^[36]線の配置を正確に計算するには、入力座標の数倍の数値精度が必要です。線が線上の 2 つの点で指定されている場合、配置の頂点の座標には、これらの入力点の 4 倍の精度が必要になる場合があります。そのため、計算幾何学者は限られた数値精度で配置を構築するためのアルゴリズムも研究してきました。^[37]${\displaystyle O(n^{2})}$${\displaystyle O(n^{2})}$${\displaystyle O(n)}$

同様に、研究者たちは、ゾーン、^[38]、 レベル、^[39]、または与えられた点の集合を含むセルの集合など、配置のより小さな部分を構築するための効率的なアルゴリズムを研究してきました。^{[40]中央の}座標を持つ配置の頂点を見つける問題は、ロバスト統計学では、点の集合のTheil-Sen推定値を計算する問題として（双対形式で）発生します。 ^[41]${\displaystyle k}$${\displaystyle x}$

マーク・ファン・クレフェルトは、直線配置の頂点間の最短経路を計算するアルゴリズム問題を提案した。このアルゴリズムでは、経路は配置のエッジに沿っているように制限されており、配置グラフ全体に最短経路アルゴリズムを適用するのにかかる2乗時間よりも高速である。 ^[42]近似アルゴリズムは既知であり、^[43]問題は少数の平行なファミリーに分類される直線（都市の街路網で典型的）に対しては効率的に解くことができるが、^[44]一般的な問題は未解決のままである。^[45]

擬似直線配置は、直線配置と同様の位相特性を共有する曲線の族である。 ^{[46]これらは、}射影平面において、任意の 2 つの曲線が単一の交差点で交わる単純な閉曲線として定義できる。 ^[47]擬似直線配置は、直線配置と組み合わせ的に同等である場合に伸縮可能であると言われる。伸縮可能性の判定は難しい計算作業である。実数の存在理論では、伸縮可能な配置と伸縮不可能な配置を区別することは完全である。 ^[48]有限個の擬似直線の配置はすべて、「スプレッド」内の線になるように拡張できる。スプレッドとは、位相平面のすべての 2 つの点が (ユークリッド平面のように) 一意の線で接続される非ユークリッド接続幾何学の一種であるが、ユークリッド幾何学の他の公理は適用されない可能性がある。^[49]

非ユークリッド幾何学のもう一つの種類は双曲平面であり、この幾何学における直線の配置も研究されてきた。^[50]ユークリッド平面における任意の有限の直線集合は、双曲平面において組合せ的に同値な配置を持つ（例えば、配置の頂点を大きな円で囲み、円の内部を双曲平面のクラインのモデルとして解釈することによって）。しかし、平行な（交差しない）直線のペアは、ユークリッド平面よりも双曲直線配置の方が制約が少ない。特に、平行である関係はユークリッド直線については同値関係であるが、双曲直線については同値関係ではない。^{[51]双曲配置における直線の}交差グラフは、任意の円グラフになり得る。擬似直線の双曲的直線配置に対応する概念は、弱い擬似直線配置である^[52] 。これは、直線と同じ位相特性を持つ曲線の族^[53]であり、族内の任意の2つの曲線は、単一の交差点で交わるか、交差点を持たない。^[52]

パンカジ・アガルワルとミカ・シャリルは、配置に関する調査で、配置の研究はヤコブ・シュタイナーによるものだと述べ、「このテーマに関する最初の論文はおそらく」シュタイナーの1826年の論文であると書いている。^[54]この論文で、シュタイナーは配置が持つことができる異なるタイプの特徴の最大数の上限を証明した。^[55]シュタイナーの後、配置の研究は超平面の高次元配置へと移り、その全体構造とこれらの配置内の単一セルに焦点が当てられた。線の配置、およびこれらの配置内のゾーンなどのより複雑な特徴の研究は、計算幾何学の基礎の一部として1980年代から再び注目を集めるようになった。^[54]

• 構成（幾何学）、すべての線が同じ数の点を含み、すべての点が同じ数の線に属する線の配置と点の集合
• 配置（空間分割）、曲線や面が平坦である必要はなく、曲線を重ねて作った平面、または面を重ねて作った高次元空間の分割。
• 数学橋は、イギリスのケンブリッジにある橋で、梁がアーチの接線に沿って配置されています。

• 組み合わせ的に異なる線配置のデータベース