離散幾何学

離散幾何学（りさんきかがく、英: discrete geometry）または組合せ幾何学（くみあわせきかがく、英: combinatorial geometry）とは、離散的な幾何的対象についての組合せ的な性質および構成手法について研究する幾何学の一分野である。離散幾何学のほとんどの問題は点、直線、平面、円、球面、多角形などの基本的な幾何的対象の有限または離散的な集合にまつわるものであり、この主題ではそれらが「どのように交叉するか」や「どのようにより大きな対象を被覆しうるのか」といった組合せ的な性質に焦点を当てる。

離散幾何学は凸幾何学（英語版）や計算幾何学と多くを共有するほか、有限幾何学、組合せ最適化、デジタル幾何学（英語版）、差分幾何学（英語版）、幾何的グラフ理論（英語版）、トーリック幾何学、組合せ位相幾何学（英語版）とも近い関係にある。

歴史

多面体や図形の敷き詰めはケプラーやコーシーのような人々によって長きにわたって研究されてきたが、現代的な離散幾何学の起源は19世紀後半である。初期に研究されたテーマはテュー（英語版）による円充填の密度や、レイ（英語版）とシュタイニッツ（英語版）による射影配置（英語版）、ミンコフスキーによる数の幾何学（英語版）、そして、テイト、ヒーウッド（英語版）、ハドウィガー（英語版）による地図の彩色だった。

ラースロー・フェイェス・トート（英語版）、H・S・M・コクセター、ポール・エルデシュが離散幾何学の基礎を築いた^[1][2][3]。

トピック

多面体とポリトープ

ポリトープ（超多面体）は平坦な縁を持つ幾何的対象である。これは任意の一般の次元数について存在する。多角形は2次元、多面体は3次元、多胞体は4次元のポリトープである。一部の理論ではこの概念がさらに一般化され、非有界な多面体（無限胞体（英語版）や図形の敷き詰め）や抽象多面体（英語版）のような対象までもが含まれる。

離散幾何学においてポリトープを研究する切り口のいくつかを以下に挙げる。

• 多面体組合せ論（英語版）
• 格子凸多面体（英語版）
• エルハート多項式
• ピックの定理
• ハーシュ予想（英語版）

充填、被覆、敷き詰め

充填、被覆、そして敷き詰めは、いずれも一定の対象（典型的には円、球、タイル）をある規則にしたがって曲面や多様体上に配置する方法である。

球充填はある格納空間の中での互いに重なり合うことのない球の配置である。球は全て同一の大きさであるものと考え、空間は3次元ユークリッド空間であることが普通であるが、異なる球や一般の次元のユークリッド空間（2次元なら円充填、高次元では超球充填）、あるいは双曲空間（英語版）のような非ユークリッド空間を考慮するように充填問題を一般化することもできる。

平面の敷き詰めとは、重なったり隙間ができたりしないように、タイルと呼ばれる単一または複数の幾何的図形を平面に貼ることである。これも高次元に一般化される。

この領域の具体的なトピックには以下が含まれる。

• 円充填
• 球充填
• ケプラー予想
• 準結晶
• 非周期タイリング（英語版）
• 周期グラフ（英語版）
• 細分割規則（英語版）

構造の剛性と柔軟性

構造剛性はリンク機構やヒンジのような関節で連結された剛体の複合物の可動性について説明する組合せ的な理論である。

この領域のトピックには以下が含まれる。

• コーシーの定理（英語版）
• フレキシブル多面体（英語版）

接続構造

接続構造は、その公理的定義に見出せるように、（アフィン（英語版）、射影、メビウス（英語版）などの）平面を一般化する。接続構造はそれらの高次元のものについても一般化するものであり、有限の構造は時に有限幾何と呼ばれる。

形式的には、接続構造とは3つ組

${\displaystyle C=(P,L,I).\,}$

のことである。ここで、P は「点」の集合、L は「直線」の集合、そして、I ⊆ P × L は 接続（英語版） 関係である。I の元は旗（英語版）と呼ばれる。また、

${\displaystyle (p,l)\in I,}$

であるとき、点 p は直線 l 上にあるという。

この領域のトピックには以下が含まれる。

• 点と直線の配置（英語版）
• 直線アレンジメント（英語版）
• 超平面アレンジメント（英語版）
• 建物

有向マトロイド

有向マトロイドは、有向グラフの性質や順序体上の線型空間（特に順序線型空間（英語版））におけるベクトル同士の位置関係の性質を抽象化する数学的構造である^[4]。なお、通常の（非有向）マトロイドは、有向とは限らないグラフや順序づけられているとは限らない線型空間におけるベクトル同士の位置関係の性質を抽象化するものである^[5][6]。

幾何的グラフ理論

幾何的グラフとは頂点や辺（中国語版、フランス語版）が幾何的対象と関連付けられているグラフのことである。例えば、ユークリッドグラフ、多面体やポリトープの1-スケルトン（英語版）、単位円板グラフ（英語版）、可視性グラフ（英語版）が挙げられる。

この領域のトピックには以下が含まれる。

• グラフ彩色
• 多面体グラフ
• ランダム幾何的グラフ（英語版）
• ボロノイ図とドロネー三角形分割

単体複体

単体複体とは点、線分、三角形や、それらの高次元版である単体を同じ次元の面で貼り合わせることによって構成される、ある種の位相空間である。より抽象的な概念であり現代的な単体的ホモトピーの理論に現れる単体的集合（英語版）と混同してはならない。単体複体の純粋に組合せ論的な対応概念は抽象単体複体（英語版）である。ランダム幾何的複体（英語版）も参照。

位相的組合せ論

位相幾何学に組合せ論の概念を用いた組合せ位相幾何学は、20世紀前半になると代数的位相幾何学へと発展した。

1978年、ラースロー・ロヴァースによるクネーザー予想の証明によって、組合せ論の問題を解くために代数的位相幾何学の手法が用いられるという逆の状況が生じ、新たな位相的組合せ論の研究が始まった。ロヴァースの証明に用いられたボルスク–ウラムの定理（英語版）はこの新しい分野において重要な役割を果たしているほか、多くの等価・類似の命題が存在し、公平分割問題の研究に用いられている。

この領域のトピックには以下が含まれる。

• スペルナーの補題（英語版）
• 正則地図（英語版）

格子と離散群

離散群とは離散位相を備えた群のことであり、この位相により位相群となる。また、ある位相群の離散部分群とは相対位相が離散であるような部分群のことである。例えば、（通常の距離位相を伴う）整数 Z の加法群は実数 R の加法群の離散部分群となるが、有理数 Q の加法群はそうではない。

局所コンパクトな位相群における格子とは商位相空間が有限な不変測度を持つ離散部分群のことである。Rⁿ の部分群の特別な場合については、これは通常の幾何的概念としての格子にあたるものであり、格子の代数的構造と全ての格子の全体の幾何に対しての理解が比較的進んでいる。1950年代から1970年代にわたって得られたボレル、ハリシュ＝チャンドラ（英語版）、モストウ、玉河、M・S・ラグナサン（英語版）、マルグリス、ジマー（英語版）の深い結果は、種々の例を提示するとともに理論の多くを局所体上の冪零なリー群と半単純代数群（英語版）の設定に一般化した。1990年代にはバス（英語版）とルボツキ（英語版）が木格子の研究を創始し、現在も活発な研究分野である。

この領域のトピックには以下が含まれる。

• 反射群（英語版）
• 三角群（英語版）

デジタル幾何学

デジタル幾何学では、2Dや3Dのユークリッド空間のオブジェクトをデジタイズした画像やモデルとみなされるような離散集合（多くは離散点集合）を取り扱う。

単純に言えば、デジタイズとはオブジェクトをその点の離散集合に置き換えることである。テレビ画面や新聞で目にする画像も、コンピュータのラスタ表示も、実はデジタル画像なのである。

主な応用領域はコンピュータグラフィクスや画像解析である^[7]。

差分幾何学

差分幾何学とは微分幾何学の概念に対応する離散の概念の研究分野である。滑らかな曲線や曲面の代わりに、多角形やメッシュ、単体複体が登場する。コンピュータグラフィクスや位相的組合せ論の研究に用いられる。

この領域のトピックには以下が含まれる。

• 離散ラプラス作用素（英語版）
• 外差分法（英語版）
• 和分差分学
• 離散モース理論（英語版）
• スペクトル形状解析（英語版）

関連項目

• Discrete and Computational Geometry（英語版）（論文誌）
• 離散数学
• ポール・エルデシュ

脚注

参考文献

• Bezdek, András (2003). Discrete geometry: in honor of W. Kuperberg's 60th birthday. New York, N.Y: Marcel Dekker. ISBN 0-8247-0968-3 
• Bezdek, Károly (2010). Classical Topics in Discrete Geometry. New York, N.Y: Springer. ISBN 978-1-4419-0599-4 
• Bezdek, Károly (2013). Lectures on Sphere Arrangements - the Discrete Geometric Side. New York, N.Y: Springer. ISBN 978-1-4614-8117-1 
• Bezdek, Károly; Deza, Antoine; Ye, Yinyu (2013). Discrete Geometry and Optimization. New York, N.Y: Springer. ISBN 978-3-319-00200-2 
• Brass, Peter; Moser, William; Pach, János (2005). Research problems in discrete geometry. Berlin: Springer. ISBN 0-387-23815-8 
• Pach, János; Agarwal, Pankaj K. (1995). Combinatorial geometry. New York: Wiley-Interscience. ISBN 0-471-58890-3. https://archive.org/details/combinatorialgeo0000pach 
• Goodman, Jacob E. and O'Rourke, Joseph (2004). Handbook of Discrete and Computational Geometry, Second Edition. Boca Raton: Chapman & Hall/CRC. ISBN 1-58488-301-4 
• Gruber, Peter M. (2007). Convex and Discrete Geometry. Berlin: Springer. ISBN 978-3-540-71132-2 
• Matoušek, Jiří (2002). Lectures on discrete geometry. Berlin: Springer. ISBN 0-387-95374-4 
• Vladimir Boltyanski, Horst Martini, Petru S. Soltan (1997). Excursions into Combinatorial Geometry. Springer. ISBN 3-540-61341-2