1. 近傍枝探索における近傍矩形の大きさ

最終的な主張はTheorem1であり、それを証明するためにLemma1と2を示す。

1.1. Lemma1

$0<r\le d$, $\partial L\equiv \{x\in R^2\mid \parallel x{\parallel }_{\infty }=d\}$を定める。

半径$r$上の円周上の点を$(x,y{)}^T\in R^2(x\ne 0,y\ne 0)$の接線と$L$には2つの交点が存在するが、その2点間の距離(${\ell }_2$ノルム)を$l(x,y)$とおくと、$|x|=|y|=\frac{r}{\sqrt{2}}$の時に最小値$2(\sqrt{2}d-r)$をとる

(proof)

対称性より$0<x<r,0<y<r$を満たす円周上の点についてのみ考えれば良いので、以下ではそこに限って話を進める。

一般に半径$r>0$の円周上の点$(x_0,y_0)\in R^2$の接線の方程式は以下で与えられる。 $$x_{0}x+y_{0}y=r^2$$ ゆえに円周上の点$(x,y{)}^T(0<x,y<r)$を通る接線は以下の2点を通る。 $$p_1(x,y)\equiv {(d,\frac{r^2-dx}{y})}^T,p_2(x,y)\equiv {(\frac{r^2-dy}{x},d)}^T$$ この2点間の距離$l(x,y)$の二乗は極座標表示を用いると以下のように表される。 $$\begin{array}{cc}{\left(l\right(x,y\left)\right)}^2& =\parallel p_1(x,y)-p_2(x,y){\parallel }_2^2\\ & ={\left(\frac{r^2-d(x+y)}{x}\right)}^2+{\left(\frac{r^2-d(x+y)}{y}\right)}^2\\ & =\frac{(r^2-d(x+y\left){)}^2\right(x^2+y^2)}{x^2{y}^2}\\ & =\frac{r^2(r^2-d(x+y){)}^2}{x^2{y}^2}\\ & =\frac{r^4(r-d(\cos \theta +\sin \theta ){)}^2}{r^4{\sin }^2\theta {\cos }^2\theta }\\ & =f\left(\theta \right)\end{array}$$ $$\begin{array}{cc}{\left(l\right(x,y\left)\right)}^2& =\parallel p_1(x,y)-p_2(x,y){\parallel }_2^2\\ & ={\left(\frac{r^2-d(x+y)}{x}\right)}^2+{\left(\frac{r^2-d(x+y)}{y}\right)}^2\\ & =\frac{(r^2-d(x+y\left){)}^2\right(x^2+y^2)}{x^2{y}^2}\\ & =\frac{r^2(r^2-dr(\cos \theta +\sin \theta ){)}^2}{r^4{\sin }^2\theta {\cos }^2\theta }\\ & =\frac{(r-d(\cos \theta +\sin \theta ){)}^2}{{\sin }^2\theta {\cos }^2\theta }\\ & =f\left(\theta \right)\end{array}$$

ここで、 $$f\left(\theta \right)=\frac{(r-d(\cos \theta +\sin \theta ){)}^2}{{\sin }^2\theta {\cos }^2\theta }$$ と定義した。ゆえに、上記の問題は開区間$(0,\frac{\pi }{2})$における$f\left(\theta \right)$の最小値を求める問題に帰着される。まず、$f$の微分$f^{\prime }$を求める。 $$({\sin }^2\theta {\cos }^2\theta {)}^{\prime }=2\sin \theta \cos \theta ({\cos }^2\theta -{\sin }^2\theta )$$ であるので、 $$\begin{array}{cc}{f}^{\prime }\left(\theta \right)& =\frac{2\sin \theta \cos \theta (r-d(\sin \theta +\cos \theta \left)\right)(\cos \theta -\sin \theta )(-d\sin \theta \cos \theta -(r-d(\sin \theta +\cos \theta )\left)\right(\cos \theta +\sin \theta \left)\right)}{{\sin }^4\theta {\cos }^4\theta }\\ & =\frac{2(r-d(\sin \theta +\cos \theta \left)\right)\left(d\right(1+\sin \theta \cos \theta )-r)(\cos \theta -\sin \theta )}{{\sin }^3\theta {\cos }^3\theta }\end{array}$$ まず、$r-d(\sin \theta +\cos \theta )$について評価する。

$\sin \theta +\cos \theta =\sqrt{2}\sin (\theta +\frac{\pi }{4})$であり、$0<\theta <\frac{\pi }{2}$より$\frac{\pi }{4}<\theta +\frac{\pi }{4}<\frac{3}{4}\pi$であるので、 $$1<\sin \theta +\cos \theta <\sqrt{2}$$ ゆえに、 $$r-d(\sin \theta +\cos \theta )<r-d\le 0$$ 続いて$d(1+\sin \theta \cos \theta )-r$を評価する。

$0<\theta <\frac{\pi }{2}$の時に$0<\sin \theta ,\cos \theta$であるので $$d(1+\sin \theta \cos \theta )-r>d-r\ge 0$$ 最後に$\cos \theta -\sin \theta$の評価を行う。

$\cos \theta -\sin \theta =-\sqrt{2}\sin (\theta -\frac{\pi }{4})$であり$0<\theta <\frac{\pi }{2}$より$-\frac{\pi }{4}<\theta -\frac{\pi }{4}<\frac{\pi }{4}$であるので、

$-\frac{\pi }{4}<\theta -\frac{\pi }{4}<0$つまり$0<\theta <\frac{\pi }{4}$のとき$\cos \theta -\sin \theta >0$

$0\le \theta -\frac{\pi }{4}<\frac{\pi }{4}$つまり$\frac{\pi }{4}\le \theta <\frac{\pi }{2}$のとき$\cos \theta -\sin \theta \le 0$

以上をまとめると、$0\le \theta <\frac{\pi }{4}$の時$f^{\prime }\left(\theta \right)\le 0$であり$\frac{\pi }{4}\le \theta <\frac{\pi }{2}$のとき$f^{\prime }\left(\theta \right)\ge 0$である。

ゆえに、$(0,\frac{\pi }{2})$の範囲で$f\left(\theta \right)$は$\theta =\frac{\pi }{4}$の時に最小値$4(\sqrt{2}d-r{)}^2$をとる。

ゆえに、半径$r$上の円周上の点を$(x,y{)}^T\in R^2(x\ne 0,y\ne 0)$の接線と$\partial L$には2つの交点が存在するが、その2点間の距離$l(x,y)$は$|x|=|y|=\frac{r}{\sqrt{2}}$の時に最小値$l(x,y)=\sqrt{|4(\sqrt{2}d-r{)}^2|}=2(\sqrt{2}d-r)$をとる。

1.2. Lemma2

$0<r\le d$, $\partial L\equiv \{x\in R^2\mid \parallel x{\parallel }_{\infty }=d\}$を定める。

半径$r$の閉円板$D\equiv \{x\in R^2\mid \parallel x{\parallel }_2\le r\}$と共通部分を持つ任意の直線と$L$には2つの交点が存在するが、その2点間の距離(${\ell }_2$ノルム)を$l(x,y)$とおくと、$|x|=|y|=\frac{r}{\sqrt{2}}$の時に最小値$2(\sqrt{2}d-r)$をとる。

ただし、$d=r$で$x$軸もしくは$y$軸に平行な直線の場合のみ、交点が無数に存在するので、その時の距離$l(x,y)$は$d$と定める。

上記の結果より、長さが$2(\sqrt{2}d-r)$以下の任意の線分は$D$との共通部分を持つなら、少なくとも片方の端点は$L\equiv \{x\in R^2\mid \parallel x{\parallel }_{\infty }\le d\}$に含まれる。

(proof)

(i)原点を通る直線の場合

$(-d,0{)}^T$と$(d,0{)}^T$の2つの交点を持つか、$(0,-d{)}^T$と$(0,d{)}^T$の2つの交点を持つ場合が距離が最小で2点間の距離は$2d$

(ii)原点と直線の距離が$r^{\prime }(0<r^{\prime }\le r)$で$x$軸もしくは$y$軸に平行な直線の場合

$d=r$の場合の距離は仮定の定義より$d$で$d>r$の場合は距離は$2d$

(ii)原点と直線の距離が$r^{\prime }(0<r^{\prime }\le r)$で$x$軸と$y$軸に平行でない直線の場合

Lemma1より$|x|=|y|=\frac{r^{\prime }}{\sqrt{2}}$を満たす$(x,y)$を通る直線が2点間の距離を最小にし、その時の距離は$2(\sqrt{2}d-r^{\prime })$となる。

以上より、$|x|=|y|=\frac{r}{\sqrt{2}}$を通る直線の時、2点間の距離が最小となりその

時の距離は$2(\sqrt{2}d-r)$

1.3. Theorem1

道路ネットワークの枝の最大長さ${\ell }_{max}>0$が与えられているとする。

位置座標が与えられた時に、その座標との距離が$r>0$以下である枝を取得したいとする。(ノルムは${\ell }_2$を用いる)

そのために、少なくとも1つの端点が$L\equiv \{x\in R^2\mid \parallel x{\parallel }_{\infty }\le d\},d\ge r$に含まれる枝を全て抽出するという方法をとるとする。

この時、距離が$r>0$以下である枝を全て抽出するための$d$の必要十分条件は

$$2(\sqrt{2}d-r)\ge {\ell }_{max}\iff d\ge \frac{1}{2\sqrt{2}}({\ell }_{max}+2r)$$

(proof)

Lemma2から従う。

2. Backup

ゆえに元の問題は$f(x,y)$の$0<x,y<r$における最小値を求める問題に帰着される。ここで$x\uparrow r$のとき$y\downarrow 0$となるので$f(x,y)$の分母は$0$に近づく、一方で$x+y\to r$となるので$d>r$の時は$f(x,y)\to \infty$となる。$d=r$の時は$c\equiv x+y$とおくと、 $$xy=\frac{1}{2}\left(\right(x+y{)}^2-(x^2+y^2))=\frac{1}{2}(c^2-r^2)$$ となるので、 $$f(x,y)=\frac{r^2(r-(x+y){)}^2}{x^2{y}^2}=\frac{4r^2(r-c{)}^2}{(c^2-r^2{)}^2}=\frac{4r^2}{(r+c{)}^2}$$ であるので、$x\uparrow r$の時$c=x+y\to r$となり$f(x,y)=1$となる。この時$L(x,y)=r$となっている。$x\downarrow 0$の時も同様の結果が得られるので、$L(x,y)<r$を満たす広義の極値のうち$L(x,y)$が最小のものをLagrange未定乗数法を用いて求める。 $$\begin{array}{cc}{f}_x(x,y)& =\frac{-2d{x}^2{y}^2(r^2-d(x+y\left)\right)-2x{y}^2(r^2-d(x+y){)}^2}{x^4{y}^4}\\ & =\frac{-2(dx+r^2-d(x+y\left)\right)(r^2-d(x+y\left)\right)}{x^3{y}^2}\\ & =\frac{-2(r^2-dy)(r^2-d(x+y\left)\right)}{x^3{y}^2}\end{array}$$ であり、$(x,y)$の対称性から $$f_y(x,y)=\frac{-2(r^2-dx)(r^2-d(x+y\left)\right)}{x^2{y}^3}$$