線の配置

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

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

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

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

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

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

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

同じ点の分類と、同じ同値類の形状は、無限だが局所的に有限な配置にも使用できます。これは、平面のすべての有界部分集合が有限個の線で横断される配置として定義されます。^{[ 2 ]}この場合、非有界セルは無限に多くの辺を持つ可能性があります。^{[ 3 ]}

配置における頂点、辺、セルの最大数を数えるのは簡単であり、それらはすべて線の数の2乗に比例する。

• との取り決め${\displaystyle n}$行は最大${\displaystyle n(n-1)/2}$頂点（三角数）は、交差する線1組につき1つずつ存在する。この最大値は、単純な配置、つまり各2本の線が他のすべての線とは互いに素な頂点で交差する場合に達成される。いくつかの線が平行である場合、またはいくつかの頂点が2本以上の線によって交差される場合、頂点の数は少なくなる。^{[ 4 ]}
• 必要に応じて、軸に平行な線を避けるために配置を回転させることができます。このステップの後、配置のエッジを形成する各光線は、その端点から上または下のいずれかに伸びます。水平にはなれません。${\displaystyle n}$下向きの光線は、1行につき1本ずつで、これらの光線は分離します。${\displaystyle n+1}$配置の中で下方向に境界のないセル。残りのセルはすべて一意の最下頂点を持つ（軸に平行な線がないため）。各線ペアについて、2本の線が最下頂点で交わるセルは1つしか存在しないため、下方向に境界のあるセルの数は最大で線ペアの数である。${\displaystyle n(n-1)/2}$無制限セルと制限セルを合計すると、配置内のセルの総数は最大で${\displaystyle n(n+1)/2+1}$^{[ 5 ]}これらは怠惰なケータリング業者の数列の数字です。^{[ 6 ]}
• 配置の辺の数は最大で${\displaystyle n^{2}}$これは、頂点とセルの数からオイラー標数を用いて計算するか、各線が最大で に分割されることを観察することによって確認できる。${\displaystyle n}$端はもう一方によって${\displaystyle n-1}$線。シンプルな配置は正確に${\displaystyle n^{2}}$エッジ。^{[ 5 ]}

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

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

射影平面では、すべての直線のペアが交点を持つため、直線の配置を研究するのが便利です。 ^{[ 17 ]}射影平面では直線が平面を2つの異なる側面に分割しないため、直線の配置を直線の側面を使用して定義することはできません。^{[ 18 ]}それでも、配置のセ​​ルをどの直線にも属さない点の連結成分、エッジを単一の直線に属する点の集合の連結成分、頂点を2つ以上の直線が交差する点として定義することは可能です。射影平面における直線の配置は、直線の両端にある2つのユークリッド光線が、その直線上の最も左の頂点と最も右の頂点を結ぶ射影平面上の1つのエッジに置き換えられ、また、無限遠で射影直線が交差する単一のセルが射影平面で置き換えられるという点で、ユークリッド平面における対応物とは異なります。^{[ 19 ]}

ユークリッド平面上の直線の配置は、2次元球面上の大円の配置として自然に解釈できる。${\displaystyle S^{2}}$これを確認するには、ユークリッド平面を埋め込んでください。${\displaystyle \mathbb {R} ^{2}}$アフィン平面として${\displaystyle A\subset \mathbb {R} ^{3}}$原点を通らない。${\displaystyle A}$原点を通る直線を決定し、${\displaystyle S^{2}}$対蹠点のペアで、同様に、すべての線は${\displaystyle A}$球面上の大円にマッピングされる。赤道は${\displaystyle A}$2つの半球を分離し、無限遠線としての役割を果たす。${\displaystyle S^{2}}$射影平面が得られる。${\displaystyle \mathbb {R} ^{2}}$大円に自然に拡張され、平行線は無限遠で交わる。このようにして、入射、領域、交点を含む線配置の組み合わせ構造は、球面上の大円配置に移行しても保持される。^{[ 20 ]}

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

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

1. 鉛筆に近い形状で、${\displaystyle n-1}$1点を通る複数の直線と、同じ点を通らない追加の直線1本。
2. 正多角形の辺と対称軸によって形成される線分群、
3. 正多角形の辺と対称軸、および無限遠線。

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

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

ロバーツの三角形定理に基づく、三角形の数が最小となる配置

17本の線で構成された小本三角形

必ずしも単体ではない配置における三角形セルの極値を調べることも興味深い。射影平面上の任意の配置は少なくとも${\displaystyle n}$三角形のみを持つすべての配置。${\displaystyle n}$三角形は単純でなければならない。^{[ 30 ]}射影配置ではなくユークリッド配置の場合、三角形の最小数は${\displaystyle n-2}$ロバーツの三角形定理により。^{[ 31 ]}単純な配置における三角形面の最大可能数は、以下によって上限が定められることが知られている。${\displaystyle n(n-1)/3}$下限は${\displaystyle n(n-3)/3}$下限は、正則グラフの対角線の特定の部分集合によって達成される。${\displaystyle 2n}$-角形。^{[ 32 ]}単純である必要のない射影配置については、${\displaystyle n(n-1)/3+4}$すべての三角形${\displaystyle n\geq 4}$、およびすべての取り決め${\displaystyle n\geq 6}$最大で${\displaystyle 7n(n-1)/18+1/3}$三角形。^{[ 33 ]}密接に関連するコボン三角形問題は、射影平面で三角形を形成する可能性のある無限面を数えずに、ユークリッド平面上の配置における重なり合わない有限三角形の最大数を求める問題である。ここでも、配置は単純である必要はない。一部の値ではあるが、すべての値ではない。${\displaystyle n}$取り決めが存在する${\displaystyle n(n-2)/3}$三角形。^{[ 34 ]}

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

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

テトラキス正方形タイル張り

三角形タイル張り

二等分された六角形のタイル張り

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

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

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

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

9本の擬似線からなる、伸縮不可能な擬似線配置。（9本未満の擬似線からなる配置はすべて伸縮可能である。）パップスの六角形定理によれば、この配置はどの体上の射影平面においても実現できない。

双曲線線配置は、三角形を含まない円グラフが5色を必要とする場合があることを示すためにAgeev（1996）が使用したコード図と組み合わせ的に等価である。

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

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

配置に関する調査において、Pankaj AgarwalとMicha Sharir は配置の研究をJakob Steinerに帰し、「このトピックに関する最初の論文はおそらく」Steiner の 1826 年の論文であると述べている。^{[ 56 ]}この論文で、Steiner は配置が持つことができる異なるタイプの特徴の最大数に関する限界を証明した。^{[ 57 ]} Steiner 以降、配置の研究は超平面の高次元配置へと移り、それらの全体構造とこれらの配置内の単一セルに焦点を当てた。直線の配置、およびこれらの配置内のゾーンなどのより複雑な特徴の研究は、計算幾何学の基礎の一部として 1980 年代から再び注目を集めるようになった。^{[ 56 ]}

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

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