ABC 314 Ex — Disk and Segments

考察

円盤の中心を決めると、必要な半径は「各線分までの距離の最大値」になる。この値は中心を動かす位置について凸なので、横座標を固定して縦方向の最小値を求め、その結果を横方向でも最小化できる。二重の三分探索を使うために、線分までの距離、探索区間、内側の近似誤差を順に確かめよう。

中心を固定して線分までの距離を測る

中心を P=(x,y)P=(x,y)、第 ii 線分を SiS_i とし、di(P)d_i(P) を点 PP から SiS_i への最短距離とする。半径 rr の閉円盤と SiS_i が共有点を持つ条件は r≥di(P)r\geq d_i(P) である。線分が円盤の内部を通っていてもよく、円周で接する必要はない。従って、中心を固定したときの最小半径は

f(x,y)=max⁡1≤i≤Ndi((x,y))f(x,y)=\max_{1\leq i\leq N}d_i((x,y))

となる。どの線分が半径を決めるかを先に場合分けするより、すべての線分までの距離を測る方が扱いやすい。

線分の端点を A,BA,B、方向ベクトルを v=B−Av=B-A とする。直線上の点は A+tvA+tv と書けるので、まず

∥P−(A+tv)∥2=∥P−A∥2−2t(P−A)⋅v+t2(v⋅v)\|P-(A+tv)\|^2 =\|P-A\|^2-2t(P-A)\cdot v+t^2(v\cdot v)

を最小にする tt を求める。ここで ⋅\cdot は内積、∥u∥\|u\| はベクトル uu の長さを表す。この二次式の最小点は

t0=(P−A)⋅vv⋅vt_0=\frac{(P-A)\cdot v}{v\cdot v}

である。ただし、線分上にある条件は 0≤t≤10\leq t\leq1 なので、t=min⁡(1,max⁡(0,t0))t=\min(1,\max(0,t_0)) と範囲内に収める。これが clamp という操作である。最近点は Q=A+tvQ=A+tv、求める距離は ∥P−Q∥\|P-Q\| になる。端点が異なるため、分母は正である。

例えば A=(0,0),B=(4,0)A=(0,0),B=(4,0) に対し、P=(2,3)P=(2,3) なら t0=1/2t_0=1/2 で最近点は線分内部の (2,0)(2,0)、距離は 33。P=(6,3)P=(6,3) なら t0=3/2t_0=3/2 を 11 に収め、最近点は端点 BB、距離は 13\sqrt{13} となる。直線までの距離だけでは後者を正しく測れない。

中心の探索区間を決める

すべての端点は正方形 [0,1000]2[0,1000]^2 内にあり、線分全体もその中にある。中心の各座標を [0,1000][0,1000] 内へ clamp した点を P′P' とする。この正方形内の任意の点 QQ に対して、各軸で P′P' の方が QQ に近いか同じなので、∥P′−Q∥≤∥P−Q∥\|P'-Q\|\leq\|P-Q\| である。特に各線分の最近点に対しても成り立ち、どの線分までの距離も増えない。

従って、最適な中心を [0,1000]2[0,1000]^2 内に選べる。内側・外側とも、探索区間を最初から [0,1000][0,1000] と固定してよい。

縦方向の最小化を横方向の探索に組み込む

後で示すように、ff は二変数を同時に動かしても凸である。横座標 xx を固定すれば、y↦f(x,y)y\mapsto f(x,y) は一変数の凸関数になる。さらに、縦方向の真の最小値を

F(x)=min⁡0≤y≤1000f(x,y)F(x)=\min_{0\leq y\leq1000}f(x,y)

と定義すると、FF も凸になる。そこで FF の最小値を外側の三分探索で求め、その一回の評価を内側の三分探索で近似する。

一変数の探索は、現在の区間 [L,R][L,R] に対して m1=L+(R−L)/3m_1=L+(R-L)/3、m2=R−(R−L)/3m_2=R-(R-L)/3 を取り、左の評価値が右以下なら R=m2R=m_2、そうでなければ L=m1L=m_1 とする。等値でも一方だけを捨てればよく、最小点が一意である必要はない。

具体的な手順は次のとおりである。

  1. eval(x,y) で全線分への距離を計算し、その最大値 f(x,y)f(x,y) を返す。
  2. inner(x) では yy の区間を [0,1000][0,1000] とし、eval(x,y) を比較して100回三分探索する。最後の区間の中点を y^(x)\widehat y(x) とし、近似値 F^(x)=f(x,y^(x))\widehat F(x)=f(x,\widehat y(x)) を返す。
  3. xx の区間も [0,1000][0,1000] とし、inner(x) を比較して100回三分探索する。最後の中点を x^\widehat x とし、inner(\widehat x) を答えとして出力する。

例えば線分が (0,0)(0,0)–(0,4)(0,4) と (4,0)(4,0)–(4,4)(4,4) なら、0≤y≤40\leq y\leq4 の範囲で f(x,y)=max⁡(x,4−x)f(x,y)=\max(x,4-x) となる。最小半径は 22 で、最適中心は (2,y) (0≤y≤4)(2,y)\ (0\leq y\leq4) のすべてである。このように、最小点が区間をなす場合も扱える。

注意したいのは、外側で比較する値が真の F(x)F(x) ではなく F^(x)\widehat F(x) であることだ。残った区間が狭いというだけでは、最適な横座標を途中で捨てた影響を評価できない。その影響も含めて、正当性節で100回の反復を許容誤差へ結び付ける。

典型の発動条件

凸関数の入れ子三分探索

少数の連続変数を最適化するとき、目的関数の凸性と、一部の変数を最小化した後の凸性を確認できれば候補になる。各座標を固定したときの凸性だけでは、部分最小化後の凸性の証明にはならない。内側の値を近似するなら、その誤差が外側の比較へ入ることも評価する。

点と線分の距離

点から線分への最短距離は、内積で直線上への射影位置を求め、係数を [0,1][0,1] へ clamp して得られる。最近点が端点となる場合を、同じ式の中で扱える。

問題固有の要素

すべての線分と共有点を持つ円盤は、中心から各線分への距離の最大値で表せる。対象が凸集合なので距離の凸性が使え、端点の座標制約から最適中心の探索域も確定できる。別の図形へ広げるときは、この二つの条件をそれぞれ確認する。

正当性

線分距離・最大値・部分最小化の凸性

一つの線分への距離を d(P)d(P) とする。二つの中心 P0,P1P_0,P_1 の最近点を、それぞれ線分上の Q0,Q1Q_0,Q_1 とする。0≤t≤10\leq t\leq1 に対し、中心を同じ比率で結んだ点 Pt=(1−t)P0+tP1P_t=(1-t)P_0+tP_1 を考える。線分上の点 Qt=(1−t)Q0+tQ1Q_t=(1-t)Q_0+tQ_1 も選べるので、三角不等式から

d(Pt)≤∥Pt−Qt∥≤(1−t)∥P0−Q0∥+t∥P1−Q1∥=(1−t)d(P0)+td(P1)\begin{aligned} d(P_t)&\leq\|P_t-Q_t\|\\ &\leq(1-t)\|P_0-Q_0\|+t\|P_1-Q_1\|\\ &=(1-t)d(P_0)+td(P_1) \end{aligned}

となる。これが線分距離の凸性である。各線分にこの不等式を適用すると、右辺はすべて (1−t)f(P0)+tf(P1)(1-t)f(P_0)+tf(P_1) 以下だから、その最大値 f(Pt)f(P_t) も同じ上限を持つ。従って ff は凸である。ここでは f(P)f(P) を中心 P=(x,y)P=(x,y) における f(x,y)f(x,y) の意味で使った。

次に、横座標 x0,x1x_0,x_1 で最小値を与える縦座標を y0,y1y_0,y_1 とする。距離は連続で探索域は閉区間なので、これらの最小点を選べる。xt=(1−t)x0+tx1x_t=(1-t)x_0+tx_1、yt=(1−t)y0+ty1y_t=(1-t)y_0+ty_1 と置くと、yty_t も [0,1000][0,1000] 内にあり、

F(xt)≤f(xt,yt)≤(1−t)f(x0,y0)+tf(x1,y1)=(1−t)F(x0)+tF(x1)\begin{aligned} F(x_t)&\leq f(x_t,y_t)\\ &\leq(1-t)f(x_0,y_0)+tf(x_1,y_1)\\ &=(1-t)F(x_0)+tF(x_1) \end{aligned}

が成り立つ。従って FF も凸である。縦方向で最適な二中心を結んだ点を、途中の横座標でも候補にできることが要点である。

近似値を比較しても、失う最小値を抑えられる

まず、中心を動かした長さ以上には距離は変化しない。中心 PP の最近点を QQ とすれば、d(P′)≤∥P′−Q∥≤∥P′−P∥+d(P)d(P')\leq\|P'-Q\|\leq\|P'-P\|+d(P) であり、逆向きも同様である。全線分の最大値についても

∣f(P′)−f(P)∣≤∥P′−P∥|f(P')-f(P)|\leq\|P'-P\|

となる。一つの座標だけを動かすときは、その座標の変化量が値の変化の上限になる。FF についても、一方の横座標で最適な縦座標をもう一方で候補にし、逆向きも考えると、∣F(x′)−F(x)∣≤∣x′−x∣|F(x')-F(x)|\leq|x'-x| となる。

内側の比較は、丸めを除けば真の f(x,y)f(x,y) 同士である。凸性により各回の区間内に最小点を残せるので、IyI_y 回後の区間幅を wyw_y とすると、中点からその最小点までの距離は高々 wy/2w_y/2 である。従って

0≤F^(x)−F(x)≤ε,ε=wy20\leq\widehat F(x)-F(x)\leq\varepsilon, \qquad \varepsilon=\frac{w_y}{2}

である。近似値は実際の中心で評価するため、真の最小値を過小評価しない。

ここから外側の一回の比較を調べる。F^(m1)≤F^(m2)\widehat F(m_1)\leq\widehat F(m_2) により右側を捨てたとすると、真の値には

F(m1)≤F(m2)+εF(m_1)\leq F(m_2)+\varepsilon

が成り立つ。もし捨てた部分に現在の区間の最小点 z>m2z>m_2 があっても、m2m_2 を m1m_1 と zz の内分点として凸性の不等式を書き直すと、

F(m2)−F(m1)m2−m1≤F(z)−F(m2)z−m2\frac{F(m_2)-F(m_1)}{m_2-m_1} \leq\frac{F(z)-F(m_2)}{z-m_2}

となる。三等分では z−m2≤m2−m1z-m_2\leq m_2-m_1 だから、整理すると

F(m2)−F(z)≤z−m2m2−m1ε≤εF(m_2)-F(z) \leq\frac{z-m_2}{m_2-m_1}\varepsilon \leq\varepsilon

を得る。残す区間には m2m_2 が含まれるので、区間内の最小値の増加は高々 ε\varepsilon である。左側を捨てる場合も左右を逆にして同じことが示せる。最小点が残る場合の増加は0であり、等値や複数の最小点もこの議論に含まれる。

従って外側を IxI_x 回繰り返しても、残った区間の真の最小値は全体最適値 r∗r^* より高々 IxεI_x\varepsilon 大きいだけである。最後の区間幅を wxw_x とすれば、中点を選ぶ損失は高々 wx/2w_x/2。最後の内側評価の誤差も足して、出力値 r^=F^(x^)\widehat r=\widehat F(\widehat x) は

0≤r^−r∗≤(Ix+1)wy2+wx20\leq\widehat r-r^* \leq (I_x+1)\frac{w_y}{2}+\frac{w_x}{2}

を満たす。探索を厳密な実数演算で考えると、wx=1000(2/3)Ixw_x=1000(2/3)^{I_x}、wy=1000(2/3)Iyw_y=1000(2/3)^{I_y} である。Ix=Iy=100I_x=I_y=100 なら両方の幅は約 2.46×10−152.46\times10^{-15}、出力値の誤差上限は約 1.26×10−131.26\times10^{-13} となり、要求される絶対誤差 10−510^{-5} に十分な余裕がある。

中心を正方形へ移す操作で最適値は変わらず、線分距離の計算は最近点を正しく選び、固定中心の必要半径は距離の最大値である。以上より、入れ子の探索は元の問題の最小半径を上の誤差内で求める。この残幅と誤差の評価は本稿で補った実数演算上の論証であり、浮動小数点演算の丸めは別途考慮する。

実装上の注意

  • 射影係数は必ず [0,1][0,1] へ clamp する。距離は最近点との座標差から hypot で求められる。制約上、零長線分はない。
  • 座標・内積・距離・探索点は long double などの浮動小数点型で扱う。最小化するのは距離の最大値であり、上で使った「座標を動かした長さが値の変化の上限」という評価を距離の二乗へそのまま転用しない。
  • 実際には丸めによって区間幅が上の実数演算の値まで縮まらず、評価値にも誤差が入る。仮に外側の各評価が真の FF に対して両側に高々 η\eta の誤差を持つなら、一回の比較で真の値が逆転する幅は高々 2η2\eta。同じ証明により、区間を捨てる損失は一回につき高々 2η2\eta となる。内側は十分高精度に評価し、実際に残った幅による誤差も含めて要求精度に余裕を持たせる。100回で得た理論値を、そのまま機械上の精度だと解釈しない。
  • 最終中点でも内側探索を実行して半径を取得し、小数点以下15桁程度を出力する。探索が高精度でも、出力時に桁を落とすと誤差条件を満たせない。

復習の核

  • 「全対象と共有点を持つ最小半径」は、中心を固定して各対象への距離の最大値へ変える。
  • 入れ子の探索では、各方向の凸性に加えて、内側を最小化した値関数の凸性を示す。最適な二中心を同じ比率で結ぶと証明しやすい。
  • 数値探索の回数は、初期幅・残幅・値の変化上限から決める。内側の近似誤差が外側の比較に与える損失も数える。

計算量と制約

時間

O(NIxIy)O(NI_xI_y)。一回の距離評価は O(N)O(N)、内側は二点比較を IyI_y 回と最後の中点評価、外側は内側評価を各回二回と最後に一回行う。距離計算の回数は N(2Ix+1)(2Iy+1)N(2I_x+1)(2I_y+1) である。

空間

O(N)O(N)。入力の線分を保存し、各探索は区間と評価値だけを持つ反復処理で行える。

制約との対応

2≤N≤1002\leq N\leq100、各端点の座標は整数で 00 以上 10001000 以下、各線分の両端は異なり、異なる線分は共有点を持たない。座標範囲は探索域の証明に、端点が異なる条件は射影の分母が正であることに使う。線分同士が交わらない条件は、凸性や距離計算には不要である。

内外100回なら距離計算は最大 100×2012=4 040 100100\times201^2=4\,040\,100 回となる。制限時間は2秒、メモリ制限は1024 MiBであり、線分ごとの方向と長さの二乗を前計算すれば各評価は定数時間の幾何演算で済む。出力の相対誤差または絶対誤差は 10−510^{-5} 以下が要求され、上の反復数は絶対誤差を抑えるために選んでいる。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Disk and Segments の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 一次元凸・単峰最適化

主題
  • 一次元凸・単峰最適化: 差分/導関数の単調性または単峰性を証明し、連続解近傍・ternary search・整数境界で最適点を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
追加で学ぶ技能
    なし
    既習技能

    主タグ: 一次元凸・単峰最適化

    補助タグ: 幾何の基本判定・配置・座標変換

    執筆: abc-explanation-author1.1.1 / revision 2

    学習の位置

    体系上の位置: 一次元凸・単峰最適化

    • 差分/導関数の単調性または単峰性を証明し、連続解近傍・ternary search・整数境界で最適点を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

    先に読む単元:

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題