κ個のミスマッチを許した点集合マッチング・アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
点集合の合同性判定や最大共通部分点集合問題は計算幾何学やパターン認識における基本的な問題である.しかしながら,この二つの問題の計算量にはかなりのギャップがある.そこで,本橋では,その中間的な問題について考察する.最大共通部分点集合問題は,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
論文 | ランダム
- Clay Mineralogy of Grey Degraded Soils and Sandy Soils as Problem in Vietnam
- 人格 A-7 青年のナルシシズムに関する研究 : ナルシシズムの2つの側面を測定する尺度の作成
- 放射線治療品質管理士の必要性と品質管理の実情JRC/JSRT/JSMP合同シンポジウム放射線治療の安全確保と quality control
- マルチメディア多地点通信サーバ : 提供機能と利用インタフェース
- 外部放射線治療施設・設備の品質保証に関する訪問調査報告(シンポジウム「処方線量の計算と検証」,第51回(鹿児島)放射線治療分科会 シンポジウム)