離散幾何学

同義語：discrete geometry組合せ幾何学combinatorial geometry

概要

前提知識: Euclid空間, 凸集合, グラフ

離散幾何学 は、平面や空間に置いた有限個（あるいは離散的に並んだ）点・直線・円・凸集合・多面体などの配置について、個数や組合せの性質を調べる分野である。「$n$ 点の間に距離 $1$ の対はいくつありうるか」「どの 3 点も一直線上にない $n$ 点の中に凸 $k$ 角形は必ずあるか」「同じ大きさの球を、互いに重ならないように 1 つの球に何個まで接するように置けるか」といった問いが典型で、問いは初等的でも答えには組合せ論・位相幾何・代数幾何・確率の方法が使われる。組合せ幾何学（combinatorial geometry）ともいう。
この記事では、分野の主な話題を既存の記事とともに案内し、分野の性格をよく表す 2 つの定理を証明する。1 つは、点と直線の接続の個数を抑える Szemerédi–Trotter の定理で、グラフを平面に描いたときの交差の個数についての交差数補題から導かれる（thm-dg-szemeredi-trotter）。もう 1 つは、$n$ 点の間の相異なる距離が $\sqrt n$ 程度以上あるという Erdős の評価である（thm-dg-distinct-distances）。

定義

この記事では、$\mathbb{R}^2$ に通常の Euclid 距離 $\lvert x-y\rvert$ を入れる（Euclid空間）。直線は $\mathbb{R}^2$ の直線、すなわち $\{x\mid a\cdot x=c\}$（$a\neq0$）の形の集合とする。

点と直線の接続

平面の有限集合 $P$ と、平面の直線の有限集合 $\mathcal{L}$ について、$p\in\ell$ となる組 $(p,\ell)\in P\times\mathcal{L}$ を接続（incidence）といい、その個数を
$$ I(P,\mathcal{L}):=\#\{(p,\ell)\in P\times\mathcal{L}\mid p\in\ell\} $$
と書く。

相異なる距離の個数

2 点以上の平面の有限集合 $P$ について、$\Delta(P):=\{\lvert x-y\rvert\mid x,y\in P,\ x\neq y\}$ とおき、その要素の個数 $\lvert\Delta(P)\rvert$ を $P$ の 相異なる距離の個数 という。

接続の個数は、点と直線の配置がどれだけ「偶然の一致」を含むかを測る。どの点もせいぜい 1 本の直線にしか乗らなければ $I(P,\mathcal{L})\le n$ であり、反対の極端として、2 点以上がそろって 2 本以上の直線に乗ることは、2 本の直線が 1 点以下でしか交わらないので起こらない。この間のどこまで接続を増やせるかが Szemerédi–Trotter の定理の内容である。

主な話題

離散幾何学の主な話題と、それを扱う記事を挙げる。表の後の節で、話題ごとに代表的な定理を短く紹介する。

話題	典型的な問い・定理	記事
点と直線の配置	すべてが一直線上にあるのではない有限個の点には、ちょうど 2 点だけを通る直線がある。点と直線の接続の個数の上界	Sylvester–Gallaiの定理、no-three-in-line 問題、この記事の thm-dg-szemeredi-trotter
距離	単位距離の対の個数、相異なる距離の個数、直径を小さくする分割、点を含む最小の円	単位距離グラフ、この記事の thm-dg-distinct-distances、Borsukの問題、Jungの定理
凸性	凸集合の族の共通部分（Helly）、点の分割（Radon）、凸包の表示（Carathéodory）、凸の位置にある点の存在	凸集合、凸包、Erdős–Szekeresの定理(凸多角形)
幾何的なグラフ	距離や交差で辺を定めたグラフの彩色・辺の本数・交差の個数	単位距離グラフ、単位円板グラフ、マッチ棒グラフ、ペニーグラフ、交差数(グラフ)
詰め込みと敷き詰め	球の詰め込みの密度、1 つの球に接する球の個数、平面の敷き詰め	接吻数、平面の円の詰め込み、球の詰め込み、平面充填、Penroseの敷き詰め
格子と格子点	格子多角形の面積、凸体の中の格子点	Pickの定理、Minkowskiの凸体定理、格子点
多面体	頂点・辺・面の個数の関係、正多面体の分類、剛性、分割合同	Eulerの公式(平面グラフ)、正多面体の分類、Cauchyの剛性定理、Bolyai–Gerwienの定理、Hilbertの第3問題
色塗りと Ramsey 型の問題	平面の彩色数、大きな配置の中に必ず現れる部分構造	単位距離グラフ、Ramsey理論、Erdős–Szekeresの定理(凸多角形)

話題どうしは互いに結びついている。たとえば単位距離の個数の上界（単位距離グラフ）と Szemerédi–Trotter の定理は、どちらも「円や直線は 2 点以下でしか交わらない」という事実を、グラフの描画の交差数を通して数え上げに変える同じ方法で示せる。点の集合から作ったグラフについて Euler の公式（Eulerの公式(平面グラフ)）を使う議論は、ペニーグラフの辺の本数や交差数(グラフ) の下界にも現れる。

話題ごとの案内

点と直線の配置. 平面の有限個の点がすべて一直線上にあるのでなければ、ちょうど 2 点だけを通る直線が必ずある（Sylvester–Gallaiの定理）。この定理は実数の平面の順序の性質に依存し、複素射影平面や有限体上の平面では成り立たない例がある。どの 3 点も一直線上にないように格子点をいくつ選べるかという問題は no-three-in-line 問題で扱う。接続の個数の上界は、この記事の thm-dg-szemeredi-trotter である。
距離. $n$ 点の間に同じ距離が何回現れうるか（単位距離グラフ）、相異なる距離が何個以上あるか（この記事の thm-dg-distinct-distances）が、Erdős が 1946 年に提起した 2 つの基本問題である。直径 $d$ の平面の有限集合は、直径が $d$ より小さい 3 つの部分に分けられ（Borsukの問題）、半径 $d/\sqrt3$ の円に収まる（Jungの定理）。
凸性. $\mathbb{R}^n$ の $n+2$ 個以上の点は、凸包が交わる 2 組に分けられ（Radon の定理）、凸集合の有限族はどの $n+1$ 個にも共通点があれば全体に共通点がある（Helly の定理）。凸包の点は $n+1$ 個以下の点の凸結合で書ける（Carathéodory の定理）。3 つとも凸集合で証明されている。平面の一般の位置にある（どの 3 点も一直線上にない）十分多くの点の中には凸 $k$ 角形の頂点をなす $k$ 点がある（Erdős–Szekeresの定理(凸多角形)）。
詰め込みと敷き詰め. 平面で 1 つの円に接するように同じ大きさの円を互いに重ならないように置くと 6 個まで、空間で同じように置く球は 12 個までである（接吻数）。格子状の円の詰め込みの中では六角形の並べ方が最も密であることは平面の円の詰め込みで示されている。
格子と多面体. 格子点を頂点とする多角形の面積は内部と周上の格子点の個数で決まり（Pickの定理）、原点に関して対称な凸集合は体積が大きければ原点以外の格子点を含む（Minkowskiの凸体定理）。面の形とつながり方が同じ 2 つの凸多面体は合同であり（Cauchyの剛性定理）、面積の等しい 2 つの多角形は有限個の多角形に切って並べ替えられる（Bolyai–Gerwienの定理）。空間でこの類似が成り立たないことが Hilbertの第3問題の答えである。

例と反例

格子の上の点と直線

$k\ge1$ とし、$P:=\{1,\dots,k\}\times\{1,\dots,2k^2\}$、$\mathcal{L}$ を直線 $y=ax+b$（$a\in\{1,\dots,k\}$、$b\in\{1,\dots,k^2\}$）の全体とする。点は $n=2k^3$ 個、直線は $l=k^3$ 本である。各直線上の $x=1,\dots,k$ の点の $y$ 座標は $ax+b\le k^2+k^2$ なので、各直線はちょうど $k$ 個の点を含み、$I(P,\mathcal{L})=k^4$ である。一方 $(nl)^{2/3}=2^{2/3}k^4$ なので、$I(P,\mathcal{L})=2^{-2/3}(nl)^{2/3}$ となる。thm-dg-szemeredi-trotter の上界は、定数倍を除いて改良できない。

上界の 3 つの項

thm-dg-szemeredi-trotter の上界の $n$ と $l$ の項も省けない。1 本の直線の上に $n$ 個の点を置き、直線をその 1 本だけにすると $l=1$、$I=n$ であり、$4n^{2/3}$ は $n$ が大きいとき $n$ より小さい。逆に 1 点を通る相異なる $l$ 本の直線をとると $n=1$、$I=l$ であり、$4l^{2/3}$ は $l$ が大きいとき $l$ より小さい。点も直線も多く、どちらも偏っていないとき（$\sqrt l\le n\le l^2$ のとき）に、主要な項 $(nl)^{2/3}$ が効く。

正 $n$ 角形の頂点の距離

正 $n$ 角形（$n\ge3$）の頂点の間の距離は、$k$ 個先の頂点への弦の長さ $2R\sin(k\pi/n)$（$1\le k\le\lfloor n/2\rfloor$）であり、相異なる距離の個数は $\lfloor n/2\rfloor$ である。正方格子 $\{1,\dots,m\}^2$ の $n=m^2$ 点では、距離の 2 乗は $u^2+v^2$（$0\le u,v< m$）の形の $2m^2$ 以下の正の整数なので、相異なる距離は $2n$ 個以下である。数論を使うと、実際には $cn/\sqrt{\log n}$ 個以下であることがわかる（Erd46 Theorem 1。この記事では証明しない）。点を規則正しく並べると、相異なる距離は少なくなる。

性質

点と直線の接続

Szemerédi–Trotter の定理

平面の $n$ 個の点の集合 $P$ と $l$ 本の直線の集合 $\mathcal{L}$ について
$$ I(P,\mathcal{L})\le4(nl)^{2/3}+4n+l $$
である。

$n=0$ なら $I=0$ なので $n\ge1$ とする。点を 1 つも含まない直線を除いても $I$ は変わらず $l$ は増えないので、どの直線も $P$ の点を 1 つ以上含むとしてよい。
グラフ $G$ を次のように作る。頂点集合は $P$ とする。各直線 $\ell\in\mathcal{L}$ の上の $P$ の点を直線に沿って並べ、隣り合う 2 点を辺で結ぶ。2 点を通る直線は 1 本しかないので、同じ 2 点が 2 つの直線から結ばれることはなく、$G$ は単純グラフである。直線 $\ell$ が $k_\ell\ge1$ 個の点を含むとき $\ell$ からは $k_\ell-1$ 本の辺ができるので、$G$ の辺の本数は
$$ m=\sum_{\ell}(k_\ell-1)=I(P,\mathcal{L})-l $$
である。
各辺を両端を結ぶ線分で描いた描画 $D$ は、交差数(グラフ) の定義「良い描画と交差数」の意味の良い描画である。実際、(D1) 辺の線分の内部には、同じ直線上の $P$ の点はない（隣り合う 2 点を結んだから）し、ほかの直線上の点もない。(D2) 端点を共有する 2 辺は、同じ直線上なら共有する端点の両側にあり、違う直線上なら 2 直線の交点が共有する端点そのものなので、ほかに共有点はない。(D3) 端点を共有しない 2 辺は、同じ直線上なら共有点がなく、違う直線上なら共有点は 1 個以下である。
$D$ の交差の個数を数える。交差する 2 辺は違う直線上にあり、2 本の直線は 1 点以下でしか交わらず、その点を内部に含む辺は各直線に 1 本以下である。よって交差の個数は直線の組の個数 $\binom l2\le l^2/2$ 以下であり、$\operatorname{cr}(G)\le l^2/2$ である。
$m\ge4n$ なら、交差数補題（交差数(グラフ) の定理「交差数補題」）により
$$ \frac{m^3}{64n^2}\le\operatorname{cr}(G)\le\frac{l^2}{2}, $$
すなわち $m^3\le32n^2l^2$ であり、$m\le32^{1/3}(nl)^{2/3}<4(nl)^{2/3}$ である。$m<4n$ の場合と合わせて、$m\le4(nl)^{2/3}+4n$ が成り立つ。$I(P,\mathcal{L})=m+l$ だから主張が従う。$\square$

この定理は Szemerédi と Trotter が示したもので、上の交差数補題による短い証明は Székely による（Sze97）。ex-dg-grid により、指数 $2/3$ は改良できない。
証明の要は、幾何の条件「2 本の直線は 1 点以下でしか交わらない」を、平面に描いたグラフの交差の個数の上界に読み替えたことにある。交差数補題は辺が多いグラフは交差が多いことを述べるので、交差が少ないことから辺、すなわち接続が少ないことが出る。直線を半径 $1$ の円に替えると、各点を中心とする円の上で隣り合う点を円弧で結ぶ同じ方法で、単位距離の対の個数の上界 $O(n^{4/3})$ が得られる（Sze97、単位距離グラフ）。ただし円弧の描画では、端点を共有する 2 本の弧がもう 1 点で交わることがあり、交差数の定義に合わせるための調整が要る。

多くの点を含む直線の本数

$2\le k$ とする。平面の $n$ 点のうち $k$ 個以上を含む直線の本数 $l$ は
$$ l\le\max\Bigl\{\frac{16n}{k},\ \frac{4096\,n^2}{k^3}\Bigr\} $$
を満たす。

$k$ 個以上の点を含む $l$ 本の直線について $I\ge kl$ である。thm-dg-szemeredi-trotter から $kl\le4(nl)^{2/3}+4n+l\le4(nl)^{2/3}+4n+\frac{k}{2}l$ なので、$\frac k2l\le4(nl)^{2/3}+4n$ であり、右辺の 2 つの項のどちらかは $\frac k4l$ 以上である。$4n\ge\frac k4l$ なら $l\le16n/k$ である。$4(nl)^{2/3}\ge\frac k4l$ なら $l^{1/3}\le16n^{2/3}/k$、すなわち $l\le4096\,n^2/k^3$ である。$\square$

相異なる距離

相異なる距離の個数の下界

$n\ge2$ 個の点からなる平面の集合 $P$ について
$$ \lvert\Delta(P)\rvert\ge\sqrt{n-\tfrac34}-\tfrac12 $$
である。とくに $\lvert\Delta(P)\rvert\ge\sqrt{n}-1$ である。

$D:=\lvert\Delta(P)\rvert$ とおく。$P$ の点のうち $x$ 座標が最小のもの、その中で $y$ 座標が最小のものを $v$ とする。ほかの点 $w$ は「$x$ 座標が $v$ より大きい」か「$x$ 座標が等しく $y$ 座標が大きい」ので、$w-v$ の偏角を $(-180^\circ,180^\circ]$ で測ると $(-90^\circ,90^\circ]$ に入る。
$v$ からほかの $n-1$ 点への距離は $K$ 種類あるとし、同じ距離に現れる点の個数の最大値を $N$ とする。$n-1\le KN$ である。距離 $r$ に $N$ 個の点 $w_1,\dots,w_N$ があるとし、偏角の小さい順に $\theta_1<\theta_2<\dots<\theta_N$ と並べる（点は相異なり、$v$ から同じ距離にあるので偏角も相異なる）。偏角はすべて $(-90^\circ,90^\circ]$ にあるので $0<\theta_j-\theta_1<180^\circ$ であり、二等辺三角形 $vw_1w_j$ から
$$ \lvert w_1-w_j\rvert=2r\sin\frac{\theta_j-\theta_1}{2}\qquad(2\le j\le N) $$
である。$\sin$ は $(0^\circ,90^\circ)$ で狭義単調増加なので、これらの $N-1$ 個の距離は相異なる。よって $D\ge N-1$ であり、また $D\ge K$ である。
したがって $N\le D+1$ かつ $n-1\le KN\le D(D+1)$ である。$D^2+D-(n-1)\ge0$ を $D\ge0$ について解いて
$$ D\ge\frac{-1+\sqrt{4n-3}}{2}=\sqrt{n-\tfrac34}-\tfrac12 $$
を得る。$\sqrt{n-3/4}\ge\sqrt n-1/2$（両辺を 2 乗して $n-\frac34\ge n-\sqrt n+\frac14$、すなわち $\sqrt n\ge1$）から後半が従う。$\square$

この証明は Erdős の 1946 年の論文による（Erd46 Theorem 1）。同じ論文で Erdős は、正方格子の一部を使えば相異なる距離を $cn/\sqrt{\log n}$ 個以下にできることを示した。下界の指数は長く $1/2$ から少しずつ改良され、Guth と Katz が $cn/\log n$ の下界を示して、指数 $1$ が正しいことが確かめられた（GK15）。この記事ではこの結果を証明しない。

反例の表

外す条件	反例	成り立たなくなること
直線（2 本が 1 点以下でしか交わらない）（thm-dg-szemeredi-trotter）	$x$ 軸上の $n$ 点 $(x_i,0)$ と、相異なる $c\neq0$ についての曲線 $y=c\prod_i(x-x_i)$ を $n$ 本	どの曲線もすべての点を通るので接続は $n^2$ 個で、$4n^{4/3}+5n$ を $n$ が大きいとき超える。2 本の曲線は $n$ 点で交わる
実数体上の平面（thm-dg-szemeredi-trotter）	有限体 $\mathbb{F}_p$ 上の平面 $\mathbb{F}_p^2$ の $p^2$ 個の点と、$ax+by=c$（$(a,b)\neq(0,0)$）で定まる $p^2+p$ 本の直線	各直線が $p$ 個の点を含むので接続は $p^3+p^2$ 個で、$4(nl)^{2/3}+4n+l$ は $p^{8/3}$ 程度なので $p$ が大きいとき超える。交差数補題の背後にある平面の位相（Eulerの公式(平面グラフ)）が使えない

補足

離散幾何学の問いの多くは Erdős に始まり、平面の点の配置という素朴な設定から、交差数補題・多項式による空間の分割（Guth–Katz の方法）・確率論的方法（確率論的方法）など、組合せ論の一般的な道具が育ってきた。凸性に関わる定理（凸集合の Helly・Radon・Carathéodory の定理）は、線形計画法（線形計画法）や計算幾何学の基礎にもなっている。同じ問いを有限体上の平面で考えると、実数の場合との違いが反例の表のように現れる。