Voronoi図

1. $\lvert x-p\rvert^2\le\lvert x-q\rvert^2$ を展開すると $-2\langle x,p\rangle+\lvert p\rvert^2\le-2\langle x,q\rangle+\lvert q\rvert^2$、すなわち $2\langle x,q-p\rangle\le\lvert q\rvert^2-\lvert p\rvert^2$ となる。$q-p\ne0$ なので、これは閉半空間で、境界は等号の集合 $L(p,q)$ である。
2. 共通部分の式は定義そのものである。閉半空間は閉凸集合で、閉凸集合の共通部分は閉凸集合である（凸集合 の命題「凸集合の共通部分」）。$\rho:=\frac12\min_{q\ne p}\lvert p-q\rvert>0$ とおき、$\lvert x-p\rvert<\rho$ とすると、三角不等式から $\lvert x-q\rvert\ge\lvert p-q\rvert-\lvert x-p\rvert>2\rho-\rho>\lvert x-p\rvert$ である。よって半径 $\rho$ の開球は $V(p)$ に含まれる。
3. $x\in V(p)\cap V(q)$ なら $\lvert x-p\rvert\le\lvert x-q\rvert$ と $\lvert x-q\rvert\le\lvert x-p\rvert$ がともに成り立つので $x\in L(p,q)$ である。$V(p)$ と $V(q)$ の内部の共通部分は開集合で $L(p,q)$ に含まれるが、超平面は空でない開集合を含まないので、その共通部分は空である。$\square$

$\lvert x-s\rvert^2=\lvert x\rvert^2-a_s(x)$ であり、$\lvert x\rvert^2$ は $s$ によらないので、$\lvert x-s\rvert$ を最小にする $s$ と $a_s(x)$ を最大にする $s$ は同じである。接平面については、$z=\lvert x\rvert^2$ の $p$ での接平面が $z=\lvert p\rvert^2+2\langle p,x-p\rangle=a_p(x)$ であることから分かる。$\square$

前半は $r$ と $N(x)$ の定義そのものである。1 を仮定すると $T\subset N(x)$ なので、半径 $r$ の球面が 2 の条件を満たす。2 を仮定し、その球面の半径を $r'$ とすると、どの母点 $s$ も $\lvert x-s\rvert\ge r'$ を満たし、$T$ の点では等号なので $r'=\operatorname{dist}(x,S)$ かつ $T\subset N(x)$ である。$\square$

$\lvert m-p\rvert=\lvert m-q\rvert=\frac12\lvert p-q\rvert$ である。ある母点 $s$ で $\lvert m-s\rvert<\frac12\lvert p-q\rvert$ とすると、$s\ne p$ で、$\lvert p-s\rvert\le\lvert p-m\rvert+\lvert m-s\rvert<\lvert p-q\rvert$ となり、$q$ の選び方に反する。よって $\lvert m-p\rvert=\operatorname{dist}(m,S)$ で、$p,q\in N(m)$ である。$\square$

要点：$C$ の外から $p$ に近づく点 $y_k$ と、$C$ の中で $y_k$ にいちばん近い点 $c_k$ をとり、$y_k-c_k$ の向きの極限を $u$ とする。

（$V(p)$ が有界でなければ $p$ は内点でない。）$V(p)$ の点の列 $x_k$ で $s_k:=\lvert x_k-p\rvert\to\infty$ となるものをとり、$u_k:=(x_k-p)/s_k$ とおく。部分列をとって $u_k\to u$（$\lvert u\rvert=1$）としてよい。母点 $q$ について $x_k-q=(p-q)+s_ku_k$ なので、$\lvert x_k-p\rvert^2\le\lvert x_k-q\rvert^2$ は
$$ s_k^2\le\lvert p-q\rvert^2+2s_k\langle p-q,u_k\rangle+s_k^2,\qquad\text{すなわち}\qquad \langle q-p,u_k\rangle\le\frac{\lvert p-q\rvert^2}{2s_k} $$
となる。$k\to\infty$ として $\langle q-p,u\rangle\le0$ がすべての $q\in S$ で成り立ち、凸結合をとって、すべての $y\in\operatorname{conv}S$ で $\langle y-p,u\rangle\le0$ となる（凸集合 の定理「凸包と凸結合」）。$p$ が内点なら、小さい $\varepsilon>0$ で $p+\varepsilon u\in\operatorname{conv}S$ となるが、$\langle\varepsilon u,u\rangle=\varepsilon>0$ なので矛盾する。
（$p$ が内点でなければ $V(p)$ は有界でない。）$\operatorname{conv}S$ は閉凸集合なので（有限個の点の凸包はコンパクト）、lem-vor-support により、すべての $q\in S$ で $\langle q-p,u\rangle\le0$ となる単位ベクトル $u$ がある。$t\ge0$ と $x:=p+tu$ について
$$ \lvert x-q\rvert^2=\lvert p-q\rvert^2+2t\langle p-q,u\rangle+t^2\ge t^2=\lvert x-p\rvert^2 $$
なので $x\in V(p)$ である。よって $V(p)$ は半直線 $\{p+tu:t\ge0\}$ を含み、有界でない。$\square$

1. $x$ を Voronoi 頂点とする。$N(x)$ の点はすべて $x$ を中心とする 1 つの円の上にあるので、(G2) により $\lvert N(x)\rvert\le3$、よって $\lvert N(x)\rvert=3$ である。円の上の 3 点は一直線上にないので、$N(x)=\{p,q,r\}$ は三角形をなし、$x$ はその外心である。prop-vor-empty により外接円の内部に母点はないので、三角形 $pqr$ は $\mathcal{D}$ に属する。逆に $t\in\mathcal{D}$ の外心 $o$ は、外接円の内部に母点がないので、prop-vor-empty により $t$ の 3 頂点の領域すべてに属する。よって $\lvert N(o)\rvert\ge3$ で $o$ は Voronoi 頂点であり、前半により $N(o)$ は $t$ の頂点の集合に等しい。$N(x)=N(y)$ なら $x,y$ はどちらも同じ三角形の外心なので $x=y$ である。以上で全単射が示された。個数は、$\mathcal{D}$ の三角形の個数 $2n-h-2$（Delaunay三角形分割 の命題「三角形と辺の個数」）に等しい。
2. $pq$ が $\mathcal{D}$ の辺なら、それを辺にもつ $\mathcal{D}$ の三角形の外心が (1) により $V(p)\cap V(q)$ に属する。
   逆に $I:=V(p)\cap V(q)\ne\emptyset$ とする。prop-vor-halfspace により $I$ は直線 $\ell:=L(p,q)$ に含まれる閉凸集合である。$m$ を $pq$ の中点、$e$ を $\ell$ の向きの単位ベクトルとし、$\ell=\{m+te:t\in\mathbb{R}\}$ と書く。
   段 1（$I\ne\ell$）。(G1) により直線 $pq$ の上にない母点 $s$ がある。直線 $pq$ は $\{y:\langle y-m,e\rangle=0\}$ なので $\langle s-m,e\rangle\ne0$ で、$e$ の符号を選んで $\langle s-m,e\rangle>0$ とする。$x_t:=m+te$ について、$\langle m-p,e\rangle=0$ から
   $$ \lvert x_t-s\rvert^2-\lvert x_t-p\rvert^2=\lvert m-s\rvert^2-\lvert m-p\rvert^2-2t\langle s-m,e\rangle $$
   であり、$t$ が大きければ負になるので $x_t\notin V(p)$ である。よって $I\ne\ell$ で、$I$ には端点 $y$ がある。
   段 2（端点は Voronoi 頂点）。端点なので、$\ell$ の向きの単位ベクトル $e'$ で、すべての $\varepsilon>0$ について $y+\varepsilon e'\notin I$ となるものがある。$y+\varepsilon e'$ は $p,q$ から等距離なので $V(p)$ に属さず、ある母点 $s_\varepsilon$ で $\lvert y+\varepsilon e'-s_\varepsilon\rvert<\lvert y+\varepsilon e'-p\rvert$ となる。母点は有限個なので、ある $s$ が $\varepsilon\to0$ となる列で現れ、極限で $\lvert y-s\rvert\le\lvert y-p\rvert$ となる。$y\in V(p)$ なので等号で、$s\in N(y)$ である。$s=p$ や $s=q$ では真の不等号が成り立たないので $s\ne p,q$ であり、$\lvert N(y)\rvert\ge3$ である。(1) により $N(y)=\{p,q,r\}$ は $\mathcal{D}$ の三角形で、$pq$ はその辺である。
   段 3（$I$ は 1 点ではない）。$N(y)=\{p,q,r\}$ の外の母点 $s$ については $\lvert y-s\rvert>\lvert y-p\rvert$ なので、$2\varepsilon:=\min_{s\notin N(y)}(\lvert y-s\rvert-\lvert y-p\rvert)$ とおくと（$N(y)$ の外に母点がなければ $\varepsilon=1$ とする）、三角不等式から $\lvert x-y\rvert<\varepsilon$ の点 $x$ ではそれらの母点が $p,q,r$ より遠い。よってこの円板の中では、$V(p)\cap V(q)$ は 3 つの母点 $p,q,r$ だけの Voronoi 図の $V(p)\cap V(q)$ と一致する。後者は 三角形の外心 の命題「3 つの母点の Voronoi 図」の 2 により $y$ を端点とする半直線なので、$I$ は $y$ から出る線分を含む。$I$ は $\ell$ の閉凸部分集合で、$\ell$ 全体でも 1 点でもないので、線分か半直線である。
   組の個数は、$\mathcal{D}$ の辺の本数 $3n-h-3$（同じ命題）に等しい。$\square$

(G1) により $\operatorname{conv}S$ は凸多角形で、その角の点 3 個以上はどれも母点なので $h\ge3$ である。thm-vor-planar の個数に代入する。$\square$