けいりう堂日記

_ 図形の問題に夢中になってきた。とりあえず２次元のミンコフスキー和を簡単に計算できないかな。この手のアルゴリズムにはカーペンターズ・アルゴリズムというのがありそう。カーペンターズ・アルゴリズムというのは、たとえばボロノイ図を描くのに、頂点の数だけアリジゴクを集めて来て、うまいこと彼らが初期位置から平面上は動かないような工夫をして、おのおのに巣を作らせると、その巣の稜線がまさにボロノイ図になる、といったような図形問題のアッと驚く解き方のことを言う。この意味では、セグメンテーションをやるのにリージョン・グローイング法をうまく使うとか、膨張と収縮を繰り返して細やかなノイズや枝を消し去る画像処理方法なども一種のカーペンターズ・アルゴリズムと言えそうに思う。とりあえず、数のおけいこセットの色板みたいなのを使えば、ミンコフスキー和を大工式で計算することはそう難しくないと思う。それを、なるべく数式だけで計算したいんだ。