計算幾何学(computational geometry)とは、点・線分・多面体などの幾何的な対象を入力とする問題について、効率のよいアルゴリズムを作り、計算量を調べる分野である。平面の $n$ 点の凸包は整列と掃引で $O(n\log n)$ で求まり、頂点を順に出力するかぎり二分決定木の深さは $\Omega(n\log n)$ である。Voronoi 図と Delaunay 三角形分割も平面で $O(n\log n)$、線分の交差 $k$ 組の列挙は平面走査で $O((n+k)\log n)$ である。浮動小数点の丸めは判定の符号を逆にすることがあり、ロバスト性が課題になる。
計算幾何学(computational geometry)とは、点・線分・多面体などの幾何的な対象を入力とする問題について、効率のよいアルゴリズムを作り、その計算量を調べる分野である。問いの形は「$n$ 個の点の 凸包 を求めるのに、どれだけの手間が要るか」である。答えは $O(n\log n)$ であり、しかもこれより速くはできない。
この記事は分野の入口である。Voronoi図・Delaunay三角形分割・VC次元 などの定理はそれぞれの記事に任せ、ここでは全体の一覧と、分野を代表する 4 つの結果を証明する。平面の凸包の掃引の算法の正しさ(thm-cg-hull)、下界(thm-cg-lower)、線分の交差の平面走査(thm-cg-sweep)、乱択逐次構成の期待値(thm-cg-random)である。最後に、実数を丸めるとアルゴリズムが正しく動かなくなる問題(ロバスト性)を扱う。
$n$ は入力の大きさ、$M$ は出力の大きさ、$k$ は交差の個数である。次元 $d$ は定数とする。
| 問題 | 最悪の場合の時間 | 所在 |
|---|---|---|
| 平面の凸包(頂点を順に) | $O(n\log n)$、出力に応じて $O(n\log M)$ | thm-cg-hull、Sei17 p. 698 |
| $d$ 次元の凸包 | $O(n\log n+n^{\lfloor d/2\rfloor})$ | Sei17 Theorem 26.3.1(p. 692) |
| 平面の Voronoi 図と Delaunay 三角形分割 | $O(n\log n)$ | For17 Table 27.2.1(p. 709) |
| 平面の線分の交差の列挙 | $O((n+k)\log n)$、さらに $O(n\log n+k)$ | thm-cg-sweep、Mou17 p. 1122 |
| 平面の分割の点の位置決定 | 前処理 $O(n\log n)$、質問 $O(\log n)$、領域 $O(n)$ | Sno17 p. 1008 |
これらに共通する道具は、整列したうえで順に処理すること、平面走査、分割統治、乱択逐次構成、幾何の問題どうしの変換である。Delaunay三角形分割 の記事の「放物面への持ち上げ」は、平面の Delaunay 三角形分割を 3 次元の凸包の下側に変える。一般に $d$ 次元の Delaunay 三角形分割は $d+1$ 次元の凸包の算法で計算できる(For17 p. 709)。領域の質問に答えるデータ構造では、VC次元 の記事の ε-ネット定理が標本の大きさを与える。
座標は実数で、四則演算と比較を 1 手で行えるとする。実数の丸めは後の節で考える。計算の手間は、これらの演算の回数で数える。
平面の 3 点 $p,q,r$ に対し
$$
\operatorname{orient}(p,q,r):=(q_x-p_x)(r_y-p_y)-(q_y-p_y)(r_x-p_x)
$$
とおく。この符号が正なら $p,q,r$ は左回り($r$ は $p$ から $q$ へ向かう直線の左側)、負なら右回り、$0$ なら 3 点は一直線上にある。
$p_x< q_x< r_x$ のとき、$\operatorname{orient}(p,q,r)>0$ は「$q,r$ を結ぶ線分の傾きが $p,q$ を結ぶ線分の傾きより大きい」ことと同値である。両辺を $(q_x-p_x)(r_x-q_x)>0$ で割ればよい($r-p=(r-q)+(q-p)$ を代入する)。
入力は相異なる点 $p_1,\dots,p_n$($n\ge2$)で、辞書式の順($x$ の順、等しければ $y$ の順)に整列してあるとする。次の操作で点の列 $L$ を作る。
これは Graham の掃引の、点を偏角でなく座標で整列する形である。整列を含めた手間の評価は Sei17 p. 698 にある。
$p_1,\dots,p_n$ がすべては一直線上にないとする。def-cg-scan の出力は、$\operatorname{conv}\{p_1,\dots,p_n\}$ の頂点をちょうど 1 度ずつ、反時計回りに並べたものである。手間は整列を除いて $O(n)$、全体で $O(n\log n)$ である。
段 1($x$ 座標が相異なるとしてよい)。 十分小さい $\delta>0$ でせん断 $(x,y)\mapsto(x+\delta y,y)$ を施すと、辞書式の順は $x$ 座標の狭義の順になる。行列式が $1$ の線形写像なので $\operatorname{orient}$ は変わらず、算法の動きも変わらない。凸包の頂点と回転の向きも保たれる。
段 2(不変量)。 $x_1< \dots< x_n$ とする。$P_i:=\{p_1,\dots,p_i\}$ の凸包の下側の境界を $\ell_i\colon[x_1,x_i]\to\mathbb{R}$、$\ell_i(x):=\min\{y\mid(x,y)\in\operatorname{conv}P_i\}$ とする。$\ell_i$ は折れ線の凸関数である。両端と傾きが実際に変わる点を $\ell_i$ の頂点と呼ぶ。次を $i$ の帰納法で示す。
($\ast$) $p_i$ を加えた直後の $L$ は、$\ell_i$ の頂点を左から順に並べた列である。
$i\le2$ は明らかである。$i-1$ で成り立つとし、$L=(q_1,\dots,q_m)$、$q_1=p_1$、$q_m=p_{i-1}$ とする。傾きは $q_1,\dots,q_m$ に沿って狭義に増える。$p_i$ を加えるときの操作で $q_{t+1},\dots,q_m$ が除かれたとすると、
段 3(まとめ)。 $i=n$ の ($\ast$) から、$L$ は下側の境界の頂点を左から並べた列である。点対称 $p\mapsto-p$ は行列式が $1$ で $\operatorname{orient}$ を保ち、順を逆にするので、$U$ は上側の境界の頂点を右から並べた列である。凸包の境界は下側と上側の境界を $p_1,p_n$ でつないだものなので、出力は反時計回りの頂点の列である。
段 4(手間)。 1 回の掃引で各点は 1 度加えられ、高々 1 度除かれる。判定 1 回ごとに点が除かれるか、その点の処理が終わるので、判定は掃引あたり高々 $2n$ 回である。$\square$
点 $(0,0),(1,1),(1,3),(2,1),(2,4),(3,2),(4,0)$ をこの順に処理する。$L$ は次のように変わる。
| 加える点 | 除く点($\operatorname{orient}$ の値) | 処理のあとの $L$ |
|---|---|---|
| $(1,3)$ | なし | $(0,0),(1,1),(1,3)$ |
| $(2,1)$ | $(1,3)$($-2$)、$(1,1)$($-1$) | $(0,0),(2,1)$ |
| $(2,4)$ | なし | $(0,0),(2,1),(2,4)$ |
| $(3,2)$ | $(2,4)$($-3$) | $(0,0),(2,1),(3,2)$ |
| $(4,0)$ | $(3,2)$($-3$)、$(2,1)$($-4$) | $(0,0),(4,0)$ |
逆順の掃引では、$(4,0),(3,2),(2,4)$ の判定で値が $0$ になって $(3,2)$ が除かれ、$U=(4,0),(2,4),(1,3),(0,0)$ を得る。出力は $(0,0),(4,0),(2,4),(1,3)$ である。$(3,2)$ は凸包の辺の上にあるが頂点ではない。
凸包を順に出力すると、整列の問題を解いたことになる。どんな判定を許しても、次の下界が成り立つ。
入力の座標を読んで 2 通りに分かれる判定を繰り返し、任意の順に並んだ $n$ 点の入力に対して凸包の頂点の添字を反時計回りの巡回列として出力する二分決定木は、深さが $\log_2((n-1)!)$ 以上である。これは $(n-1)\log_2(n-1)-(n-1)\log_2 e$ 以上なので、深さは $\Omega(n\log n)$ である。
実数 $a_1< \dots< a_n$ を固定する。置換 $\sigma$ ごとに入力 $I_\sigma$ を、第 $i$ 点が $(a_{\sigma(i)},a_{\sigma(i)}^2)$ であるものとする。放物線 $y=x^2$ は狭義凸なのですべての点が頂点であり、反時計回りの順は $x$ 座標の増える順である。したがって正しい出力は巡回列 $(\sigma^{-1}(1),\dots,\sigma^{-1}(n))$ である。$\sigma$ が異なると列 $(\sigma^{-1}(1),\dots,\sigma^{-1}(n))$ は異なる。同じ巡回列を与える列は回転の $n$ 個なので、現れる巡回列は $n!/n=(n-1)!$ 通りである。出力は葉で決まるので葉は $(n-1)!$ 個以上あり、深さ $D$ の二分木の葉は $2^D$ 個以下である。最後の評価は $m!\ge(m/e)^m$ による。$\square$
出力の順序を求めない問いにも、代数的計算木のモデルでは下界がある。$n$ 点のうちちょうど $V$ 個が頂点であるかを判定する手間は $\Omega(n\log V)$ である(Kirkpatrick–Seidel。Sei17 p. 699)。証明は葉の数え上げより難しいので、ここでは述べない。この評価は出力に応じた上界 $O(n\log M)$ と釣り合う。同じ還元で、直線の上に並んだ母点の Voronoi 図は隣接の情報から整列を与える。領域の隣接を出力する算法の深さは $\log_2(n!/2)$ 以上である。
高次元では出力そのものが大きい。Sei17 Theorem 26.3.1 の第 2 項は巡回多面体の面の個数(pp. 691–692)から来ていて、最適である。
平面走査は、垂直な直線を左から右へ動かし、直線の上の状況が変わる点だけで処理をする技法である。Bentley と Ottmann は、$n$ 本の線分の交差 $k$ 組を $O((n+k)\log n)$ で列挙する方法を与えた(Mou17 p. 1122)。全部の組を調べる $O(n^2)$ と比べ、$k$ が小さいと大きく得をする。
一般の位置の仮定。 線分の端点と交点の $x$ 座標はすべて相異なり、2 本の線分は高々 1 点を共有し、3 本が 1 点を通ることはなく、端点が他の線分の上にないとする。
状態は、現在の垂直な直線と交わる線分を高さの順に並べた平衡二分探索木である。事象の列は、$x$ 座標を鍵とする優先度つきの列で、端点をすべて入れて始める。先頭の事象を順に取り出し、次のように処理する。
一般の位置の仮定のもとで、def-cg-sweep は交差する組をすべてちょうど 1 度ずつ報告し、手間は $O((n+k)\log n)$ である。
報告が実際の交差であることと、重複がないことは算法から分かる。すべて報告されることを示す。
報告されない交点があるとして、最も左のものを $p$ とし、線分 $s,t$ の交点とする。$p$ より左の事象はすべて正しく処理されたので、$p$ の直前までの状態は実際の高さの順を表している。$p$ の直前の事象の $x$ 座標と $x_p$ の間に $x'$ をとる。
$x'$ で $s,t$ の間に別の線分 $u$ があるとする。$(x',x_p]$ に端点の事象はないので、$u$ は $x_p$ まで続く。$(x',x_p)$ に交点はないので、$u$ は $s,t$ の間にとどまる。$x_p$ で $s,t$ の高さは一致するので、$u$ は $p$ を通る。これは 3 本が 1 点を通らないという仮定に反する。
よって $s,t$ は $x'$ で隣り合っている。2 本が隣り合うようになった事象の処理で交差が調べられ、$p$ は右にあるので列に入っている。$x_p$ で取り出されて報告されるので、矛盾である。
手間:事象は $2n+k$ 個で、各事象で木と列の操作を定数回行う。列の大きさは $2n+k$ 以下、$k< n^2$ なので、1 回の操作は $O(\log n)$ である。$\square$
列挙の下界は $k$ と $n\log n$ の和なので、この結果は $\log n$ の因子の分だけ最適でない。$O(n\log n+k)$ は Chazelle と Edelsbrunner が達成し、のちに領域 $O(n)$ でも達成された(Mou17 p. 1122)。
水平な直線 $y=\ell$ を下から上へ動かす。直線より下の母点の全体を $S_\ell$ とする。$y< \ell$ の点 $z$ に対し、$D(z)$ を中心 $z$ で直線に最上点で接する閉円板とする(半径 $\ell-z_y$)。
$D(z)$ が $S_\ell$ の点を含むなら、$z$ に最も近い母点の 1 つは $S_\ell$ にある。また、$D(z)$ の内部に母点がなく、境界に 2 個以上の母点があれば、$z$ は Voronoi図 の辺か頂点の上にある。
$y\ge\ell$ の母点は $D(z)$ の内部にないので、$z$ からの距離は半径以上である。$D(z)$ に含まれる $s\in S_\ell$ の距離は半径以下なので、前半を得る。後半は、$D(z)$ の内部に母点がないことから、境界の母点が $z$ に最も近く、それが 2 個以上あるからである。$\square$
$D(z)$ が母点 $s$ を含むことは $\lvert z-s\rvert\le\ell-z_y$、すなわち $z$ が「焦点 $s$、準線 $y=\ell$ の放物線 $P_s$」の下側にあることと同じである。したがって、最も近い母点が確定した領域の上の境界は、放物線 $P_s$($s\in S_\ell$)の上側の包絡である。
算法は、この包絡に現れる弧を左から順に並べた列を保つ。隣り合う弧の境目は、補題の後半により Voronoi 図の辺をなぞる。列が変わるのは、直線が母点を通るときと、連続する 3 つの弧の母点の外接円の最上点に直線が達するときである。後者で Delaunay 三角形が 1 つ見つかる(For17 pp. 709–710)。三角形は $2n$ 個未満なので(Delaunay三角形分割 の命題「三角形と辺の個数」)、事象は $O(n)$ 個で、各事象は優先度つきの列と探索木の操作 $O(\log n)$ で処理できる。全体は $O(n\log n)$ である。以上は補題の部分を除いて算法の筋であり、弧の列の変化がこの 2 種類に尽きることなど、完全な正しさの証明はここでは述べない。
点を 1 つずつ加えて構造を更新する方法は、加える順に手間が左右される。順を一様乱数で選ぶと、期待値が簡単な議論で評価できる。「最後に加えた点はどれも同じ確率である」と、時間を逆に見る議論である。
平面の $n$ 点が、どの 3 点も一直線上になく、どの 4 点も同一円周上にないとする。順を一様乱数で選んで点を 1 つずつ加えるとき、各点を加えるときに新しくできる三角形の個数の期待値は $6$ 未満で、全体で新しくできる三角形の個数の期待値は $6n$ 未満である。
最初の $r$ 点の集合を $P_r$ とする($r\ge3$)。第 $r$ 点 $p_r$ を加えたあとの Delaunay 三角形分割の三角形のうち、$p_r$ を頂点にもたないものは外接円の内部に $P_{r-1}$ の点もないので、加える前からある。$p_r$ を頂点にもつものは加える前にはない。よって新しい三角形は、$p_r$ を頂点にもつものにちょうど等しく、その個数は $p_r$ の次数以下である。
$P_r$ を固定すると、$p_r$ は $P_r$ の点のどれも確率 $1/r$ である。$P_r$ の Delaunay 三角形分割は一意で(Delaunay三角形分割 の定理「Delaunay 三角形分割の存在と一意性」)、辺は $3r-h-3$ 本($h\ge3$)なので、次数の和は $2(3r-h-3)< 6r$ である。したがって $p_r$ の次数の条件つき期待値は $6$ 未満である。$r=1,2$ では三角形はできない。$\square$
消える三角形は一度できたものなので、その総数も $6n$ 未満である。消す三角形を探す手間を含めても、期待時間は $O(n\log n)$ である(For17 Table 27.2.1 とその説明、p. 709。探索の部分はここでは証明しない)。
上の証明は実数の正確な演算を仮定している。実際の計算機で座標を浮動小数点数で扱うと、$\operatorname{orient}$ の符号を間違えることがある。判定が互いに矛盾すると、算法は単に少し不正確な答えを返すのではなく、遠くの点を落としたり、自己交差する「凸包」を返したりする(SY17 p. 1191。Kettner らの例)。
$u:=2^{-53}$、$p:=(\frac12+41u,\frac12+48u)$、$q:=(12,12)$、$r:=(24,24)$ とする。どの座標も IEEE 754 倍精度で正確に表せる。$p=(\frac12+a,\frac12+b)$ と書くと、正確な値は $\operatorname{orient}(p,q,r)=12(b-a)$ なので、
$$
\operatorname{orient}(p,q,r)=12\cdot7\cdot2^{-53}\approx9.33\times10^{-15}>0
$$
である。一方、def-cg-orient の式を倍精度でそのまま計算すると $-5.68\times10^{-14}$ になり、符号が逆である。$(\frac12+iu,\frac12+ju)$($0\le i,j< 64$)の全 $4096$ 点を $p$ にとると、$2164$ 点で符号($0$ との区別を含む)を間違えた。これらは数値で確かめた結果であり、値は式の評価の順と丸めの規則に依存する。
3 点の座標が絶対値 $2^b$ 未満の整数なら、$\operatorname{orient}(p,q,r)$ は絶対値 $2^{2b+3}$ 未満の整数である。したがって、符号を含めて $2b+4$ ビットの整数演算で正確に計算できる。
座標の差は絶対値 $2^{b+1}$ 未満なので、2 つの積はそれぞれ絶対値 $2^{2b+2}$ 未満であり、その差は絶対値 $2^{2b+3}$ 未満である。途中の結果もすべてこの範囲に収まる。$\square$
実用の対策は主に 3 つある(SY17)。
| 外す仮定 | 例 | 成り立たなくなること |
|---|---|---|
| def-cg-scan の除く条件の等号($\le0$ を $< 0$ に) | $(0,0),(1,0),(2,0),(1,1)$ | thm-cg-hull の「頂点をちょうど」:$(1,0)$ が残る |
| 入力の順が任意であること | $x$ の順に整列済みの入力 | thm-cg-lower の下界:整列を省けて $O(n)$ で済む |
| 平面であること | 3 次元で、同じ平面にない 2 本の線分の上に $n/2$ 個ずつ置いた母点 | For17 p. 708:Voronoi 頂点が $\Omega(n^2)$ 個で、$O(n\log n)$ では出力できない |
| 3 本が 1 点を通らないこと | $[-1,1]$ の上の $y=x$、$y=0$、$y=-x$ | prf-cg-sweep の議論:$x=-\frac12$ で $y=x$ と $y=-x$ の間に $y=0$ があり、交点の直前に隣り合わない |
| 順が一様乱数であること | $a_i=(0,\frac i{m+1})$($1\le i\le m$)を加えたあと、$q_k=(1+\frac1k,0)$ を $k=1,\dots,m$ の順に加える($n=2m$。全部を少しずらして一般の位置にする) | thm-cg-random の評価:$a_i,a_{i+1},q_k$ の外接円は $x$ 軸と、$x$ 座標の積が $1$ 未満の 2 点で交わる(方べきの定理)ので $q_j$($j< k$)を含まず、各 $q_k$ で新しい三角形が $m-1$ 個以上できて合計は $n^2$ の程度である。最悪の順で手間が $n$ 倍程度に悪くなることは For17 p. 709 にある |
| 正確な演算 | ex-cg-float | thm-cg-hull の証明:$\operatorname{orient}$ の符号が信用できない |
地図の評価は Handbook の各章による。凸包は Sei17、Voronoi 図と Delaunay 三角形分割は For17、線分の交差は Mou17、点の位置決定は Sno17、ロバスト性は SY17 である。教科書は BCKO08 が標準である。thm-cg-hull・thm-cg-lower・thm-cg-sweep・thm-cg-random の証明は、ここでは定義から書き下ろした。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する