Delaunay三角形分割

要点：辺の中点 $p$ のまわりの小さな半円板が、どの三角形に覆われるかを見る。

$\lvert x-o\rvert^2-r^2=q(x)-2\langle o,x\rangle+\lvert o\rvert^2-r^2$ なので、$m(x):=2\langle o,x\rangle-\lvert o\rvert^2+r^2$ とおくと $\lvert x-o\rvert^2-r^2=q(x)-m(x)$ である。$m$ はアフィン関数で、$x=a,b,c$ では左辺が $0$ なので $m=q$ である。一直線上にない 3 点での値はアフィン関数を決めるので $m=\ell_{abc}$ である。$\square$

(1 ⇒ 2)。1 を仮定し、$t\in T$ を 1 つとる。lem-dlt-lift により、すべての $s\in S$ で $\ell_t(s)\le q(s)$ である。任意の $y\in\operatorname{conv}S$ は、ある $t'\in T$ の頂点 $w_1,w_2,w_3$ の凸結合 $y=\sum_j\mu_jw_j$ で、
$$ f_T(y)=\sum_j\mu_jq(w_j)\ge\sum_j\mu_j\ell_t(w_j)=\ell_t(y) $$
である。よって $f_T\ge\ell_t$ がすべての $t$ で成り立ち、$t$ の上では等号なので $f_T=\max_{t\in T}\ell_t$ である。アフィン関数の最大は凸関数である。
(2 ⇒ 1)。$t\in T$ の内部の点 $x_0$ と $y\in\operatorname{conv}S$ をとり、$\varphi(s):=f_T(x_0+s(y-x_0))$（$0\le s\le1$）とおく。$\varphi$ は凸で、小さい $\varepsilon>0$ について $[0,\varepsilon]$ ではアフィン関数 $\psi(s):=\ell_t(x_0+s(y-x_0))$ に等しい。凸関数の傾きの単調性（凸関数 の命題「凸関数の傾きの単調性」）から、$s>\varepsilon$ なら $\frac{\varphi(s)-\varphi(0)}{s}\ge\frac{\varphi(\varepsilon)-\varphi(0)}{\varepsilon}$ で、右辺は $\psi$ の傾きなので $\varphi(s)\ge\psi(s)$ である。$s=1$ として $f_T(y)\ge\ell_t(y)$ を得る。$y\in S$ とすると $q(y)\ge\ell_t(y)$ で、lem-dlt-lift により $y$ は $t$ の外接円の内部にない。
(1 ⇒ 3) は定義から明らかである。
(3 ⇒ 2)。要点：局所 Delaunay は、辺をはさむ 2 つの三角形の上で $f_T$ が 2 枚の平面の最大になっている（辺で下に凸に折れている）ことを言う。各辺で凸なら、線分に沿って傾きが増えるので全体で凸になる。

1. $c,d$ は直線 $ab$ の反対側にあるので、線分 $cd$ は直線 $ab$ と 1 点 $m$ で交わり、$m\ne c,d$ である。$m$ が線分 $ab$ の内部にないとし、$a,b$ の名前を入れ替えて $m=a+\sigma(a-b)$（$\sigma\ge0$）とする。すると $a=\frac{1}{1+\sigma}m+\frac{\sigma}{1+\sigma}b$ は $m$ と $b$ の凸結合で、$m$ は $c,d$ の凸結合なので、$a=\beta b+\gamma c+\delta d$（$\beta,\gamma,\delta\ge0$、和が $1$）と書ける。$a$ は線分 $bc$ の上にないので $\delta>0$ である。$q$ は凸関数で、$q(b)=\ell_{abc}(b)$、$q(c)=\ell_{abc}(c)$、lem-dlt-lift により $q(d)<\ell_{abc}(d)$ なので
   $$ q(a)\le\beta q(b)+\gamma q(c)+\delta q(d)<\beta\ell_{abc}(b)+\gamma\ell_{abc}(c)+\delta\ell_{abc}(d)=\ell_{abc}(a)=q(a) $$
   となり矛盾する。よって $m$ は $ab$ の内部の点である。
2. $m=\gamma c+\delta d$（$\gamma,\delta>0$、$\gamma+\delta=1$）と書く。$abc=amc\cup bmc$、$abd=amd\cup bmd$、$acd=amc\cup amd$、$bcd=bmc\cup bmd$ であり、4 つの小さな三角形 $amc,bmc,amd,bmd$ の上では $f_T$ と $f_{T'}$ はどちらもアフィンである。頂点 $a,b,c,d$ では両者は $q$ に等しく、$m$ では
   $$ f_T(m)=\ell_{abc}(m)=\gamma q(c)+\delta\ell_{abc}(d)>\gamma q(c)+\delta q(d)=f_{T'}(m) $$
   である。アフィン関数の大小は頂点で比べればよいので、4 つの小さな三角形の上で $f_{T'}\le f_T$ であり、ほかの三角形の上では両者は等しい。
3. $m$ は $abd$ の辺の上の点でもあるので $f_T(m)=\ell_{abd}(m)=\gamma\ell_{abd}(c)+\delta q(d)$ である。(3) の不等式と比べて $\ell_{abd}(c)>q(c)$ となり、lem-dlt-lift から結論を得る。
4. 要点：$Q:=abc\cup abd=acd\cup bcd$ は凸四角形で、ほかの三角形は $Q$ と境界でしか交わらない。
   詳しい証明を開く

   (1) から $Q=\operatorname{conv}\{a,b,c,d\}$ で、上の分解から $acd\cup bcd=Q$、$acd\cap bcd=cd$ である。$Q\cap S=\{a,b,c,d\}$（$abc$ と $abd$ について条件 1）で、$b\notin acd$、$a\notin bcd$（$m$ が $ab$ の内部の点なので、$a,b$ は直線 $cd$ の反対側にある）から、新しい三角形も条件 1 を満たす。ほかの $t''\in T$ について、$t''\cap abc$、$t''\cap abd$ は空か頂点か辺で、lem-dlt-edge により辺 $ab$ ではないから、$t''\cap Q$ は $Q$ の境界に含まれる凸集合であり、したがって $Q$ の 1 辺（$ac,cb,bd,da$ のどれか）に含まれる。たとえば $ac$ に含まれるなら $t''\cap Q=t''\cap abc$ は空・$\{a\}$・$\{c\}$・$ac$ のどれかで、$t''\cap acd$ はそれと同じ、$t''\cap bcd\subset ac\cap bcd=\{c\}$ である。ほかの辺でも同じなので条件 3 が成り立つ。条件 2 は $Q$ が変わらないので成り立つ。$\square$

要点：$\operatorname{conv}S$ の角の点から扇形に分け、残りの点を 1 つずつ加えて三角形を分割する。

1. lem-dlt-exists により三角形分割 $T_0$ がある。$T_k$ に局所 Delaunay でない内部の辺があればそれをフリップして $T_{k+1}$ とする。lem-dlt-flip により $T_{k+1}$ は三角形分割で、$f_{T_{k+1}}\le f_{T_k}$ かつ $f_{T_{k+1}}\ne f_{T_k}$ である。したがって $f_{T_0}\ge f_{T_1}\ge\cdots$ で、$j< k$ なら $f_{T_k}\ne f_{T_j}$、とくに $T_k\ne T_j$ である。$S$ の三角形分割は、頂点が $S$ にある三角形（有限個）の集合の部分集合なので有限個しかない。よってこの操作は有限回で止まる。止まった三角形分割では内部の辺がすべて局所 Delaunay なので、prop-dlt-convex の 3 ⇒ 1 により Delaunay 三角形分割である。
2. $D$ を $S$ の Delaunay 三角形分割（(1) によりある）とする。$D$ の三角形は定義から空の円をもつ。逆に、空の円をもつ三角形 $t_0=abc$ が $D$ に属することを示す。
   prop-dlt-convex により $f_D$ は凸で、$f_D=q$ を $S$ の上で満たす。$x\in t_0$ を $x=\lambda_aa+\lambda_bb+\lambda_cc$（凸結合）と書くと、凸性から $f_D(x)\le\lambda_aq(a)+\lambda_bq(b)+\lambda_cq(c)=\ell_{t_0}(x)$ である。一方、$t_0$ の外接円の内部に $S$ の点がないので、lem-dlt-lift により $S$ の上で $\ell_{t_0}\le q$ であり、prf-dlt-convex の (1 ⇒ 2) と同じ計算で $\operatorname{conv}S$ の上で $\ell_{t_0}\le f_D$ である。よって $t_0$ の上で $f_D=\ell_{t_0}$ である。
   $D$ の辺は有限個の線分なので、$t_0$ の内部の点 $x$ で、$D$ のどの辺の上にもないものがとれる。$x$ はある $t\in D$ の内部の点で、$f_D(x)=\ell_t(x)=\ell_{t_0}(x)$ である。$t\ne t_0$ と仮定すると、$t$ の頂点のうち $t_0$ の頂点でないもの $w$ がある。どの 4 点も 1 つの円の上にないので $w$ は $t_0$ の外接円の上になく、内部にもないので外部にあり、$q(w)>\ell_{t_0}(w)$ である。$t$ の頂点を $w_1,w_2,w_3$ として $x=\sum_j\mu_jw_j$（$x$ が内部の点なのですべての $\mu_j>0$）と書くと
   $$ \ell_t(x)=\sum_j\mu_jq(w_j)>\sum_j\mu_j\ell_{t_0}(w_j)=\ell_{t_0}(x) $$
   となり矛盾する。よって $t_0=t\in D$ である。
   以上から、$D$ の三角形の集合は「空の円をもつ三角形の全体」に等しく、$D$ の選び方によらない。$\square$

半直線 $XP$ が $\Gamma$ と再び交わる点を $P'$ とすると、$P$ は円の内部の点なので線分 $XP'$ の内部にあり、$P'$ は $P$ と同じく直線 $XY$ の $Q$ の側にある。$Y$ は直線 $XP'$ の上にない（直線と円の交点は $X,P'$ だけで、$Y=P'$ なら $P$ が線分 $XY$ の上に来る）。円周角の定理 の系「同じ弧に対する円周角」により $\angle XP'Y=\angle XQY$ で、三角形 $PP'Y$ の外角について $\angle XPY=\angle PP'Y+\angle PYP'>\angle PP'Y=\angle XP'Y$ である。$\square$

要点：新しい 6 つの角のどれも、古い角のどれかより大きいことを、lem-dlt-inside と角の分割で示す。

1 回のフリップで変わるのは $abc,abd$ の 6 つの角だけで、lem-dlt-flip-angle によりその最小は大きくなる。三角形分割全体の最小の角は「変わらない角の最小」と「その 6 つの最小」の小さい方なので、フリップで $\alpha$ は減らない。thm-dlt-main の 1 により、任意の $T$ からフリップをくり返すと Delaunay 三角形分割 $D_T$ に着き、$\alpha(D_T)\ge\alpha(T)$ である。
三角形分割は有限個なので、$\alpha$ を最大にする $T^\ast$ がある。$D:=D_{T^\ast}$ とすると、$\alpha(D)\ge\alpha(T^\ast)\ge\alpha(T)$ がすべての $T$ で成り立ち、1 を得る。2 の仮定のもとでは thm-dlt-main の 2 により Delaunay 三角形分割は 1 つしかないので、それが 1 の $D$ である。$\square$

要点：すべての三角形の内角の和を、三角形ごとと頂点ごとの 2 通りに数える。