|
ボロノイ図を作り、２直線の角の二等分線との交点とボロノイ図の頂点についてチェックする。
ある点p(x,y)について、p1(x+dx,y+dy)とp2(x-dx,y-dy)は最も近い点と直線がpと同一である限り*1max(f(p1),f(p2))>f(p)を満たすことを示す。
dy==0となるように座標系を回転させる。
すなわちp(x,y)についてp1(x+dx,y),p2(x-dx,y)を考える。
最も近い点の座標を(x',y')とする。
dxだけ移動させた時の最も近い直線からの距離の変化をa*dxとする。
f(p1)-f(p)==(x+dx-x')^2-(x-x')^2+a*dx
f(p2)-f(p)==(x-dx-x')^2-(x-x')^2+a*(-dx)
整理して
f(p1)-f(p)==dx^2+2dx(x-x')+adx>2dx(x-x')+adx
f(p2)-f(p)==dx^2-2dx(x-x')-adx>-2dx(x-x')-adx
よってf(p1)-f(p)>0またはf(p2)-f(p)>0
すなわちmax(f(p1),f(p2))>f(p)
以上より最も近い点と直線がpと同一になるように対称に微小距離ずつ移動させることのできる点はfの最大値を与えない。
ボロノイ図と２直線の角の二等分線を重ねあわせた図を考えるとチェックすべき点はこの図の交点および頂点であることがわかる。
上の解法が適用できるのはfがどのような性質を持つときなのか考察する。
ボロノイ図・２直線の角の二等分線を使っているのはfがdist_road・dist_pointについて単調増加であるためなのでこれは必要である。
証明に用いたfの性質はある直線上で点を動かした時に上に凸な極大点がないことなので、そのような関数は上の解法が適用できる。
例えばf=dist_road+√dist_pointは上の解法が適用できない。
*1：直線をまたぐ場合は別に扱う必要があるが簡単なので省略する
