[TOC]

0.1. 平行線のfree_space

$V$を内積$⟨\cdot ,\cdot ⟩$が定まっている$R$上のベクトル空間とする.

$V$上の2つの平行な直線$P^{\prime }\left(s\right)=p_0+s(p_1-p_0),Q^{\prime }\left(t\right)=q_0+t(q_1-q_0)$を考える.

ただし,$p_1-p_0\ne 0$, $q_1-q_0=\alpha (p_1-p_0)\alpha \in R\setminus \left\{0\right\}$とする.

この時,free space

$F_{ϵ}\equiv \left\{\right(s,t)\in R^2\mid \parallel P^{\prime }(s)-Q^{\prime }(t)\parallel \le ϵ\}$は

空集合または,傾き$\frac{1}{\alpha }$の2本の平行線で囲まれた領域(横軸は$s$に対応)のいずれかである.

Proof

$p_s\equiv P^{\prime }\left(s\right)$と簡易表示をして$p_s$と$Q^{\prime }\left(t\right)$との距離$d(p_s,Q^{\prime }(t\left)\right)$を求める. $$\begin{array}{cc}d(p_s,Q^{\prime }(t){)}^2& =\parallel q_0+t\alpha (p_1-p_0)-p_s{\parallel }^2\\ & =⟨(q_0-p_s)+t\alpha (p_1-p_0),(q_0-p_s)+t\alpha (p_1-p_0)⟩\\ & ={\alpha }^2\parallel p_1-p_0{\parallel }^2(t+\frac{⟨p_1-p_0,q_0-p_s⟩}{\alpha \parallel p_1-p_0{\parallel }^2})-{\left(\frac{⟨p_1-p_0,q_0-p_s⟩}{\parallel p_1-p_0\parallel }\right)}^2+\parallel q_0-p_s{\parallel }^2\end{array}$$ また,$p_{s+\delta }=P^{\prime }(s+\delta )=p_s+\delta (p_1-p_0)$であるので, $$\begin{array}{cc}d(p_{s+\delta },Q^{\prime }(t){)}^2& ={\alpha }^2\parallel p_1-p_0{\parallel }^2(t+\frac{⟨p_1-p_0,q_0-p_s⟩}{\alpha \parallel p_1-p_0{\parallel }^2}-\frac{\delta }{\alpha })-{\left(\frac{⟨p_1-p_0,q_0-p_s⟩}{\parallel p_1-p_0\parallel }\right)}^2+\parallel q_0-p_s{\parallel }^2\end{array}$$ ここで, $$\begin{array}{cc}{F}_{ϵ}\left(s\right)& \equiv \{t\in R\mid \parallel P^{\prime }(s)-Q^{\prime }(t)\parallel \le ϵ\}\\ & =\{t\in R\mid d(p_s,Q^{\prime }\left(t\right))\le ϵ\}\\ & =\{t\in R\mid d(p_s,Q^{\prime }\left(t\right){)}^2\le {ϵ}^2\}\end{array}$$ と定義すると,$d(p_s,Q^{\prime }(t){)}^2$は$t$に関する二次式であり,$d(p_{s+\delta },Q^{\prime }(t){)}^2$は$d(p_s,Q^{\prime }(t){)}^2$を$t$軸の方向に$\frac{\delta }{\alpha }$だけ平行移動させたものになっている.ゆえに以下の2つのうちのどちらかが成り立つ.

(1)任意の$s\in R$に対して$F_{ϵ}\left(s\right)=\varnothing$である

(2)$F_{ϵ}\left(s\right)=[m_s,M_s]$とすると, 任意の$\delta \in R$に対して,$F_{ϵ}(s+\delta )=[m_s+\frac{\delta }{\alpha },M_s+\frac{\delta }{\alpha }]$が成立よって$F_{ϵ}$は傾き$\frac{1}{\alpha }$の2本の平行線で囲まれた領域(横軸は$s$に対応)となる.

0.2. Lemma3(線分のfree_space)

$P,Q$を$R^2$上の線分とする.$P$の端点を$p_0,p_1$とし$P:[0,1]\to R^2:s\mapsto p_0+s(p_1-p_0)$,$Q$についても同様に定義する.この時,free space $F_{ϵ}\equiv \left\{\right(s,t)\in [0,1{]}^2\mid \parallel P\left(s\right)-Q\left(t\right)\parallel \le ϵ\}$は

$L_2$のときintersection of unit square with an ellipse

$L_1,L_{\infty }$のときparalleogram

いずれにせよconvexである.

Proof

$P^{\prime }\left(S\right):R\to R^2:s\mapsto p_0+s(p_1-p_0)$,$Q^{\prime }\left(t\right)$についても同様に定義する.

また,$f:R^2\to R^2:(s,t)\mapsto P^{\prime }\left(s\right)-Q^{\prime }\left(t\right)$と定義する.このとき, $$f(s,t)=(p_1-p_0,-(q_1-q_0\left)\right)\left(\begin{array}{c}s\\ t\end{array}\right)+(p_0-q_0)=A\left(\begin{array}{c}s\\ t\end{array}\right)+b$$ where $A=(p_1-p_0,-(q_1-q_0\left)\right)$, $b=p_0-q_0$

となるのでaffne mapの定義の(ex)より)$f$はaffine mapである.

また,$D_{ϵ}\equiv \{x\in R^2\mid \parallel x\parallel \le ϵ\}$と定義すると,$F_{ϵ}=f^{-1}\left(D_{ϵ}\right)\cap [0,1{]}^2$であることに注意する.

(1) $P,Q$が平行でないとき

$p_1-p_0,-(q_1-q_0)$は一次独立であるので$A$はinvertible.よって,$f$の逆写像$f^{-1}:R^2\to R^2:y\to A^{-1}(y-b)$が存在しアフィン変換.

$L_2$の場合楕円のアフィン変換は楕円であるので$f^{-1}\left(D_{ϵ}\right)$は楕円である

$L_1,L_{\infty }$の場合$D_{ϵ}$は平行多面体(parallelepipeds)であり平行多面体のアフィン変換による像は平行多面体平行多面体)であることから$f^{-1}\left(D_{ϵ}\right)$も平行多面体である.

(2) $P,Q$が平行であるとき

任意の$s\in R$に対して

$p_s\equiv P^{\prime }\left(s\right)=p_0+s(p_1-p_0)$

$g_s:R\to R^2:t\mapsto (q_0-p_s)+t(q_1-q_0)$

$D_{ϵ}\left(s\right)\equiv \{t\in R\mid \parallel Q^{\prime }(t)-p_s\parallel \le ϵ\}=\{t\in R\mid \parallel g_s(t)\parallel \le ϵ\}$

と定義すると$D_{ϵ}\left(s\right)$はIntervalである.

実際,任意の,$t_1,t_2\in D_{ϵ}\left(s\right)$と任意の$\lambda \in [0,1]$に対して,任意のR上のベクトルは凸関数であることに注意すると, $$\begin{array}{cc}\parallel g_s(\lambda t_1+(1-\lambda \left)t_2\right)\parallel & =\parallel (q_0-p_s)+(\lambda t_1+(1-\lambda \left)t_2\right)(q_1-q_0)\parallel \\ & =\parallel \lambda \left\{\right(q_0-p_s)+t_1(q_1-q_0\left)\right\}+(1-\lambda )\left\{\right(q_0-p_s)+t_2(q_1-q_0\left)\right\}\parallel \\ & \le \lambda \parallel (q_0-p_s)+t_1(q_1-q_0)\parallel +(1-\lambda )\parallel (q_0-p_s)+t_2(q_1-q_0)\parallel \\ & =\lambda \parallel g_s\left(t_1\right)\parallel +(1-\lambda )\parallel g_s\left(t_2\right)\parallel \\ & \le max\{\parallel g_s(t_1)\parallel ,\parallel g_s(t_2)\parallel \}\\ & \le ϵ\end{array}$$ より,$\lambda t_1+(1-\lambda )t_2\in D_{ϵ}\left(s\right)$であるので$D_{ϵ}\left(s\right)$はIntervalである.また, $$\parallel g_s\left(t\right)\parallel =\parallel (q_0-p_0)+t(q_1-q_0)\parallel \ge |t|\parallel q_1-q_0\parallel -\parallel q_0-p_0||$$ であり,$q_1-q_0\ne 0$であるので,$\parallel q_1-q_0\parallel >0$であるので$D_{ϵ}\left(s\right)$は有界である.

次に$D_{ϵ}\left(s\right)\ne \varnothing$ならば上限を含むこと背理法で示す.

$t_1\equiv sup{D}_{ϵ}\left(s\right)$と定義して,$t_1\notin D_{ϵ}\left(s\right)$と仮定して矛盾を導く

$h:R\to R:t\mapsto \parallel g_s\left(t\right)\parallel$と定義すると$g_s$と任意のnormはcontinuousなのでその合成写像である$h$も連続.$t_1\notin D_{ϵ}\left(s\right)$であるので$ϵ<\parallel g_s\left(t_1\right)\parallel$であることに注意すると$t_1$での連続性から$\delta >0$が存在して$t_1-\delta <t<t_1$ならば$ϵ<\parallel g_s\left(t\right)\parallel$が成立するがこれは上限の定義に矛盾. よって$t_1\in D_{ϵ}\left(s\right)$である.

下限に関しても同様の議論が行えるので$D_{ϵ}\left(s\right)$は空集合もしくは閉区間である.

また,$P,Q$は平行であるので$\alpha \ne 0$を用いて$p_1-p_0=\alpha (q_1-q_0)$と表される.任意の$\delta \in R$に対して,$p_{s+\delta }=p_s+\delta (p_1-p_0)$, $g_{s+\delta }\left(t\right)=(q_0-p_s)+(t-\delta \alpha )(p_1-p_0)$であるので,

$D_{ϵ}\left(s\right)=[m,M]$ならば$D_{ϵ}(s+\delta )=[m+\delta \alpha ,M+\delta \alpha ]$であるので,$f^{-1}\left(D_{ϵ}\right)$は傾き$\alpha$の2本の平行線に囲まれた閉領域

$D_{ϵ}\left(s\right)=\varnothing$ならば$D_{ϵ}(s+\delta )=\varnothing$であるので$f^{-1}\left(D_{ϵ}\right)$は空集合