κ個のミスマッチを許した点集合マッチング・アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
点集合の合同性判定や最大共通部分点集合問題は計算幾何学やパターン認識における基本的な問題である.しかしながら,この二つの問題の計算量にはかなりのギャップがある.そこで,本橋では,その中間的な問題について考察する.最大共通部分点集合問題は,d次元ユークリッド空同上の二つの点集合P,Qが与えられた時に,Qの部分集合と合同となる最大要素数のPの部分集合を計算する問題であるが,本橋では,PとQがほとんど同じ場合,より具体的には,最大共通部分点集合の大きさが(|P|+|Q|-κ)/2以上となる場合について,いくつかの効率的なァルゴリズムを関連する結果とともに示す.主要な結果として,2次元の場合におけるO(k^3n^<1,34>+κn^2logn)時間アルゴリズムを示すが,これはkが小さい場合には既存のO(n^<3,2>logn)時間アルゴリズム(ただし,n={|P|,|Q|})より効率的なものとなっている.
- 2004-04-15
論文 | ランダム
- カナダの新進作家たち(アニメーション)
- ジャン・コワニョンの「なしの木」とベルギーのアニメーション
- 大藤賞というものについて(SOFT FOCUS/アニメーション)
- カナダとベルギーのアニメ
- アニメーション (1970年度映画評論ベストテン(特集))