■

早めに退社。電車の中で「任意の点の集合を包含する最小の円の中心座標と直径を求める」アルゴリズムを考える。基本情報技術者試験に出題された問題らしい。その内容はC言語で解法アルゴが実装されており虫食い部分を埋めるという問題形式。どうせならアルゴリズム自体を考えさせるべきだろう。

この問題を解くための、数学的に美しいアルゴリズムを考えることも可能だろう。しかし、そのためには結構高度な数学知識が必要になる。生憎と高度な数学知識は持ち合わせていないので、ここでは実用重視のアルゴリズムを考えてみる。ちなみに基本情報技術者試験に問題に書かれているC言語で実装されたアルゴも実用重視であった。

1. 任意点集合の重心を計算し、これを仮中心Cとする
2. 仮中心Cと各任意点との距離を計算。最も遠い点Pの距離maxdistを求める。
3. 仮中心CをベクトルCP方向に移動する。移動量はベクトルCPの長さに移動量係数αをかけた値。αの初期値は0.5とする。
4. ここで仮中心の移動量と予め決めたしきい値と比較。移動量が有る程度小さければこの仮中心を真中心とする。
5. 移動量が大きければ、2.以降の処理をLOOPMAX回繰り返す。
6. LOOPMAX回の繰り返し処理が終了した段階で移動量係数αを半減して2.から繰り返す。
7. 真中心が確定した段階で、真中心から最も遠い点までの距離が半径となる。