擬似線の配置
Pseudolines arranged largely to study arrangements of lines
擬似回線配置の配線図
フリードリヒ・レヴィが構築した擬似直線配置は、パップスの定理に違反しているため直線化できない[1]

擬似直線の配置は、直線配置と同様の位相特性を持つ曲線の族である。[2] [3]直線配置 の研究では、擬似直線は、各直線が他のすべての直線とちょうど1回交差するという単純な特性を持つ。これらは、射影平面において、任意の2本が1つの交差点で交わる単純な閉曲線として定義できる。 [2] [4]さらに、単純な（または均一な[5]）配置では、すべての直線が他のすべての直線と交差する必要があるが、3本の擬似直線が同じ点で交差することはない。

有限個の擬似直線の配置はすべて、「スプレッド」内の直線になるように拡張することができる。スプレッドとは、位相平面上のすべての2点が（ユークリッド平面のように）一意の直線で接続される非ユークリッド入射幾何学の一種であるが、ユークリッド幾何学の他の公理は適用されない可能性がある。[6]

配線図は、配線を表す一般的な図で、一連の平行線と、それらの間の交差を単純な交差における「X」として描きます。[1]この方法で描く場合、各線が他の線と交差する順序、各交差点間の順序の状態（または順序が重要でない交差のグループ）のいずれかの表記法で記述できます。または、交差した2本の線のラベルを各ペアとして、指定された方向（通常は左から右）に並べたペアのリストとして記述できます。配線図は組紐に似ていますが、どの交差が他の交差の上にあるのかを記録する必要がないため、交差はコクセター群の要素と見なすことができます。

2つの配置が「三角形反転によって関連付けられている」とは、三角形の1つの面の向きを変えることによって、つまり三角形を形成する3本の擬似直線の1本を他の2本の擬似直線の交点を横切るように移動させることによって、一方が他方に変換できる場合を言う。1からnまで順番に番号が付けられた任意の2つの単純な配線図について、これらの三角形反転の連続によって、一方を他方に変換することができる（逆もまた同様である）。この事実は、有向マトロイドの突然変異や、縮約分解におけるコクセター関係という用語にも相当する。 [1]

フェルスナーとヴァルトルは2009年に、擬似直線の配置に対して、単純配置はせいぜい 個存在することを証明した。これは、1992年と1997年の の境界値を改善するものである。[7]彼らはまた の下限値も証明し、これは2024年にキューナストらによって、十分に大きいに対して に改良された。[8]射影平面において、マークされたセルを持つn本の擬似直線の単純配置の数は、 n =13 まで知られている。 n {\displaystyle n} 2 0.657 n 2 {\displaystyle 2^{0.657n^{2}}} 2 0.792 n 2 {\displaystyle 2^{0.792n^{2}}} 2 0.697 n 2 {\displaystyle 2^{0.697n^{2}}} 2 0.1887 n 2 {\displaystyle 2^{0.1887n^{2}}} 2 0.2721 n 2 {\displaystyle 2^{0.2721n^{2}}} n {\displaystyle n}

1, 1, 1, 2, 3, 16, 135, 3315, 158830, 14320182, 2343203071, 691470685682, 366477801792538 ( OEISの配列A006247 )

回線配置数の増加率は擬似回線配置数の増加率に比べて小さいが、擬似回線の場合は、回線の場合はである。[8] [9] A n = 2 Θ ( n 2 ) {\displaystyle A_{n}=2^{\Theta (n^{2})}} A n = 2 Θ ( n log ⁡ n ) {\displaystyle A_{n}=2^{\Theta (n\log n)}}

伸縮性

非接近型（上）と接近型（下）の擬似線配置

擬似直線配置は、直線配置と組み合わせ的に等価である場合、伸縮可能であると言われる。つまり、各直線の交差順序を維持しながら、各直線を直線化することができる。伸縮不可能な擬似直線配置の代表的な例としては、フリードリヒ・レヴィが構築した9本の擬似直線の配置（パップスの定理に違反）や、10本の擬似直線の配置（デザルグの定理に違反）などが挙げられる。[1]対称的な擬似直線配置の中には伸縮可能なものもあるが、対称的な直線配置には伸縮できないものもある。 [5]

伸縮可能性は、与えられた擬似直線配置が直線配置と等価であるかどうかを判断する問題であり、単純伸縮可能性は、単純な配置に対する同じ問題です。[10]伸縮可能性の判断は難しい計算タスクです。実数体の存在理論では、伸縮可能な配置と伸縮不可能な配置を区別することは完全ですが、 [5] [10]単純伸縮可能性の判断はNP 困難です。[10]伸縮可能性に対するアルゴリズムは存在しており、ボコウスキーのゴムバンド法、[11]最終多項式法、[12] [13]可解列法、不等式簡約法などがあります。[1] [14]これらは、伸縮可能性の問題がランク 3 の指向マトロイドの実現の問題と等価であるという事実を利用しています。

接近擬似直線の配置とは、各擬似直線のペアが交差するまで互いに接近し、その後互いに離れる擬似直線の配置である。接近擬似直線では実現できない擬似直線の配置もあり、それらは一般に伸縮可能ではない。しかし、すべての接近配置が伸縮可能であるわけではない。[9]このような接近配置は、一連の三角形の反転によって他の任意の配置に変換できる。言い換えれば、接近配置は連結された反転グラフを持つ。

有向マトロイド

上の配置には、下には σ ( a , b , c ) = + {\displaystyle \sigma (a,b,c)=+} σ ( a , b , c ) = − {\displaystyle \sigma (a,b,c)=-}

ランク3の有向マトロイドは擬似直線の配列と等価であり、また、一様である有向マトロイド（独立集合が最大でr個の要素を含む集合であり、rは固定された整数）は、 単純な擬似直線の配列と等価である。したがって、ある形式を扱うためのツールは、どちらの研究においても、その等価形式を分析するために使用することができる。[1]

与えられた擬似直線配置に対応する 3-シグノートープまたはキロトープは次のように定義されます。 に対する の符号は、3つの擬似 直線、、およびによって形成される三角形の方向を表します。と が の下で交差する場合、 です。と がの上で交差する場合、 です。[15]同様に、がの前で交差する場合は、が の後で交差する場合は です。ここで、各擬似直線には方向が指定されていると仮定します (配線図で各擬似直線に暗黙的な方向があり、それぞれが左から右に向いているなど)。3 本の線がすべて同じ点で交差する場合は です。 σ {\displaystyle \sigma } σ ( a , b , c ) {\displaystyle \sigma (a,b,c)} a < b < c {\displaystyle a<b<c} a {\displaystyle a} b {\displaystyle b} c {\displaystyle c} a {\displaystyle a} c {\displaystyle c} b {\displaystyle b} σ ( a , b , c ) = + {\displaystyle \sigma (a,b,c)=+} a {\displaystyle a} c {\displaystyle c} b {\displaystyle b} σ ( a , b , c ) = − {\displaystyle \sigma (a,b,c)=-} a {\displaystyle a} b {\displaystyle b} c {\displaystyle c} σ ( a , b , c ) = + {\displaystyle \sigma (a,b,c)=+} a {\displaystyle a} b {\displaystyle b} c {\displaystyle c} σ ( a , b , c ) = − {\displaystyle \sigma (a,b,c)=-} σ ( a , b , c ) = 0 {\displaystyle \sigma (a,b,c)=0}

配置グラフ

擬似線配置グラフは、単純な擬似線配置によって誘導されるグラフであり、頂点は交差点に対応し、辺は擬似線に沿って隣接する頂点同士を接続します。線配置グラフは、線配置と同様に定義されます。[16]

擬似直線配置グラフは、その構造的特性を利用するアルゴリズムによって線形時間で認識できる。[17]擬似直線配置グラフは2頂点連結であり、すべての次数2および次数3の頂点に隣接する頂点を追加すると3頂点連結となり、一意の平面埋め込み（「標準埋め込み」）を与える。対照的に、直線配置グラフの認識は直線による幾何学的実現可能性の検証（伸縮性の判定）を必要とするため、 ∃完全 R {\displaystyle \mathbb {R} } （したがってNP困難）である。[16] [10]

これらのグラフには他にも注目すべき組み合わせ特性がいくつかある: [18] [19]

  • これらは4辺彩色可能、3頂点彩色可能である。
  • 擬似直線上の直径は、構造に依存しない。 n {\displaystyle n} n − 2 {\displaystyle n-2}
  • 頂点が正対となるのは、それが外面上にある場合のみである。
  • それらの次数列は完全に特徴付けられる：実現可能な列は、、、およびの形をとる；のとき、は奇数でなければならない ⟨ 4 d 4 , 3 d 3 , 2 d 2 ⟩ {\displaystyle \langle 4^{d_{4}},3^{d_{3}},2^{d_{2}}\rangle } 3 ≤ d 2 ≤ n {\displaystyle 3\leq d_{2}\leq n} d 3 = 2 ( n − d 2 ) {\displaystyle d_{3}=2(n-d_{2})} d 4 = n ( n − 5 ) / 2 + d 2 {\displaystyle d_{4}=n(n-5)/2+d_{2}} d 2 = n {\displaystyle d_{2}=n} n {\displaystyle n}
  • すべてがハミルトン的であるわけではないが[16] 、球面配置グラフは常にハミルトン的である[18]。

あらゆる- 頂点擬似直線配置グラフは、面積 のグリッドに線形時間で描画できる。[17]幅は擬似直線配置の最大kレベル複雑度に依存する。これは離散幾何学における主要な未解決問題である。これらのグラフは、サイズ の普遍点集合も許容する。これは、一般的な平面グラフの二次境界よりもはるかに小さい。[17]配置グラフの描画は、平面性パズルにおける主要な課題である。[17] n {\displaystyle n} O ( n 7 / 6 ) {\displaystyle O(n^{7/6})} O ( n log ⁡ n ) {\displaystyle O(n\log n)}

コーボン三角形問題

19本の線を並べると、三角形の数が最大になります（107個）。

コーボン三角形問題は、藤村コーボン（1903-1983）によって初めて提唱された組合せ幾何学における未解決問題である。この問題は、 k本の直線の配列上に辺が重なり合わない三角形の最大個数を求めるものである。 N ( k ) {\displaystyle N(k)}

直線配置問題は、しばしば二つの部分に分けられます。一つは擬似直線配置を用いた同値問題、もう一つは最適な三角形数を持つ配置の伸縮可能性の問題です。これにより、パップスの定理やデザルグの定理のような規則に違反することを心配することなく、純粋な組合せ論や群論を活用することができます。[1] [20]

参照

  • ルーカス・フィンシー博士、「有向マトロイドのホームページ」
  • 離散幾何学と計算幾何学ハンドブック

参考文献

  1. ^ abcdefg フェルスナー、ステファン、グッドマン、ジェイコブ・E. (2017). 「擬似線配置」(PDF) .離散幾何学および計算幾何学ハンドブック（第3版）. チャップマン・アンド・ホール/CRC. ISBN  9781315119601。
  2. ^ ab Grünbaum, B. (1972)、「配置と広がり」、数学地域会議シリーズ、第10巻、プロビデンス、ロードアイランド州：アメリカ数学会、40ページ
  3. ^ Agarwal, PK ; Sharir, M. (2002)、「擬似直線配置：双対性、アルゴリズム、およびアプリケーション」、Proc. 13th ACM-SIAM Symposium on Discrete Algorithms (SODA '02)、サンフランシスコ：Society for Industrial and Applied Mathematics、pp.  800– 809
  4. ^ エップスタイン、D. ;ファルマーニュ、J.-Cl. ; Ovchinnikov, S. (2007)、メディア理論、シュプリンガー・フェルラーク
  5. ^ abc Shor, PW (1991), 「擬似直線の伸縮性はNP困難」, Gritzmann, P.; Sturmfels, B. (編), 応用幾何学と離散数学: Victor Klee記念論文集(PDF) , DIMACSシリーズ離散数学と理論計算機科学, 第4巻, プロビデンス, RI: アメリカ数学会, pp.  531– 554
  6. ^ グッドマン、ジェイコブ・E. ;ポラック、リチャード; ウェンガー、レファエル ; ザムフィレスク、チューダー (1994)、「すべての配置は広がりまで広がる」、コンビナトリカ、14 (3): 301– 306、doi :10.1007/BF01212978、MR  1305899、S2CID  42055590
  7. ^ Felsner, Stefan; Valtr, Pavel (2011). 「擬似線分の符号化と計数配置」(PDF) .離散幾何学と計算幾何学. 46 (3). Springer Science+Business Media: 405– 416. doi :10.1007/s00454-011-9366-4 . 2025年6月19日閲覧。
  8. ^ ab コルテス・キューナスト、フェルナンド;ダラント、ジャスティン。フェルスナー、ステファン。 Scheucher, Manfred (2024)、An Improvement Lower Bound on the Number of Pseudoline Arrangements、Leibniz International Proceedings in Informatics (LIPIcs)、Schloss Dagstuhl – Leibniz-Zentrum für Informatik、arXiv : 2402.13107、doi : 10.4230/LIPIcs.SoCG.2024.XX (2025 年 7 月 6 日に非アクティブ) {{citation}}: CS1 maint: DOI inactive as of July 2025 (link)
  9. ^ ab Felsner, Stefan; Pilz, Alexander; Schnider, Patrick (2022). 「接近擬似直線の配置」(PDF) .離散幾何学と計算幾何学. 67 (2). Springer: 380– 402. doi :10.1007/s00454-021-00361-w. PMID  35221404. 2025年6月14日閲覧.
  10. ^ abcd Schaefer, Marcus (2010)、「いくつかの幾何学的および位相的問題の複雑性」(PDF)、グラフ描画、第17回国際シンポジウム、GS 2009、シカゴ、イリノイ州、米国、2009年9月、改訂論文、Lecture Notes in Computer Science、vol. 5849、Springer-Verlag、pp.  334– 344、doi : 10.1007/978-3-642-11805-0_32、ISBN  978-3-642-11804-3、 2021年6月26日にオリジナルからアーカイブ（PDF） 、 2024年10月16日閲覧
  11. ^ Bokowski, Jürgen (2008)、「曲面の実現を見つけるためのヒューリスティックな方法について」、Bobenko, A.I.; Schröder, P.; Sullivan, JM; Ziegler, GM (eds.), On Heuristic Methods for Finding Realizations of Surfaces、オーバーヴォルフアッハ・セミナーズ、第38巻、バーゼル、スイス：ビルクハウザー出版社、pp.  255– 260、ISBN  978-3-7643-8621-4、 2025年6月19日閲覧
  12. ^ Lombardi, Henri (1990)、「Nullstellensatz réel effectif et variantes」(PDF)、CR Acad. Sci. Paris Sér. I、Théorie des Nombres、ブザンソン、310 (Fascicule 1)、フランシュ＝コンテ大学: 635– 640、doi :10.5802/pmb.a-60 、2025年6月19日閲覧
  13. ^ 福田 孔明; 宮田 博之; 森山 園子 (2013)「小さな実現可能な有向マトロイドの完全列挙」,離散幾何学と計算幾何学, 49 : 359–381 , arXiv : 1204.0645 , doi :10.1007/s00454-012-9493-7 (2025年7月4日現在非アクティブ) {{citation}}: CS1 maint: DOI inactive as of July 2025 (link)
  14. ^ ボコウスキー、ユルゲン; Sturmfels、Bernd (1989)、Computational Synthetic Geometry、Lecture Notes in Mathematics、vol. 1355、シュプリンガー・フェルラーク・ベルリン・ハイデルベルク、土居：10.1007/BFb0089253、ISBN  978-3-540-50478-8、 2025年6月19日閲覧
  15. ^ バーゴールド、ヘレナ;フェルスナー、ステファン。マンフレッド・シューチャー（2023）。シグノトープの拡張定理。第 39 回計算幾何学国際シンポジウム (SoCG 2023)。ライプニッツ国際情報学会議 (LIPIcs)。 Vol. 258. ダグシュトゥール情報局ライプニッツツェントルム城。 17:1–17:16ページ。arXiv : 2303.04079。土井：10.4230/LIPIcs.SoCG.2023.17。
  16. ^ abc Bose, Prosenjit; Everett, Hazel; Wismath, Steve (2003). 「配置グラフの特性」.国際計算幾何学応用ジャーナル. 13 (6): 447– 462. doi :10.1142/S0218195903001281.
  17. ^ abcd Eppstein, David (2014). 「小さなグリッドでの配置グラフの描画、あるいは平面性の活用法」. Journal of Graph Algorithms and Applications . 18 (2): 211– 231. doi : 10.7155/jgaa.00319 .
  18. ^ ab Felsner, Stefan; Hurtado, Ferran; Noy, Marc; Streinu, Ileana (2006). 「ハミルトン性と配置グラフの彩色」.離散応用数学. 154 (17): 2470– 2483. doi : 10.1016/j.dam.2006.04.006 .
  19. ^ ダス、サンディップ;ラオ、シッダニ・バスカラ。サフー、ウマカント（2021）。 「擬線配置グラフにおける度数列と離心率について」。アルゴリズムと離散応用数学 (CALDAM 2021)。コンピューターサイエンスの講義ノート。 Vol. 12601.スプリンガー。 pp.  259–271。土井:10.1007/978-3-030-67899-9_20。
  20. ^ Bartholdi, Nicolas; Blanc, Jérémy; Loisel, Sébastien (2008)「最大数の三角形を持つ P 2 {\displaystyle \mathbb {P} ^{2}} と R 2 {\displaystyle \mathbb {R} ^{2}} における直線と擬似直線の単純な配置について」(PDF)、Goodman, Jacob E.、Pach, János、Pollack, Richard (編)、「離散幾何学と計算幾何学に関する調査: ユタ州スノーバードで 2006 年 6 月 18 ～ 22 日に開催された第 3 回 AMS–IMS–SIAM 合同夏季研究会議「離散幾何学と計算幾何学 - 20 年後」の議事録、Contemporary Mathematics、vol. 453、プロビデンス、ロードアイランド：アメリカ数学会、pp.  105– 116、arXiv：0706.0723、doi：10.1090/conm/453/08797、ISBN 978-0-8218-4239-3、MR  2405679
Retrieved from "https://en.wikipedia.org/w/index.php?title=Arrangement_of_pseudolines&oldid=1324201207"