今回も『Convex Optimization』を読んでいきます．
書影を出すためにAmazonのリンクを貼ってはいますが，この本は無償公開されているので興味のある方はぜひ読んでみてください．
問題文
Let $a$ and $b$ be destinct points in $\mathbb{R}^ n$. Show that the set of all points that are closer (in Euclidean norm) to $a$ than $b$, i.e., $\{ x \mid ||x-a||_2 \leq ||x-b||_2 \}$, is a halfspace. Describe it explicitly as an inequality of the form $c^ T x \leq d$. Draw a picture.
回答
この演習問題には Voronoi Description of halfspace と書かれていました．
二点 $a$, $b$ のうち点 $a$ に近いような点 $x$ の全体が，半空間（halfspace）になっていることを示しなさいという問題です．
複数の点 $a_1, \cdots , a_k$ が与えられたときに，それぞれに最も近くなるような点の全体を図示したもののことをボロノイ図といいますから，点の数が２個のときのボロノイ図を描けという問題であるともとれます．
回答ですが，これでどうでしょうか．
まず先に境界 $\partial H$ の式を求めて，それが切り取る２つのエリアのうち点 $a$ を含む方を選ぶという方法で求めています．
感想
絵を描くとわかったつもりになりますが，平面や空間より高次元の場合でも成り立つようにしないといけないので，絵は頼りにしてはいけないんですよね．
内積って本当に便利ですね．
ところでゴールデンウィークが終わり，そろそろこのブログも更新頻度を保つのが大変になってきました．いまはまだ２日に一度ですが，さらに下げることも検討しています．．
