高次元点集合の合同性判定について
スポンサーリンク
概要
- 論文の詳細を見る
本稿では,d次元(ユークリッド)空間の二つの点集合AとB(|A|=|B|=n)が与えられた時,それらが合同であるかないかを判定する問題について考察する.まず,dを固定した時に,この問題に対するO(n^<(d-1)/2>(log n)^2)時間の確率的アルゴリズムを示す.このアルゴリズムはbirthday paradoxという良く知られた性質に基づいて構成されている.この結果は既知の結果(O(n^<d-2>log n)時間)を大きく改善するものである.そして,dを固定しない場合,この問題がグラフの同型性判定問題と同程度以上に困難であることを示し,また,関連する他の問題についても議論する.
- 一般社団法人情報処理学会の論文
- 1994-03-17
著者
関連論文
- 最小キーおよび最適部分構造スクリーンの近似
- 二つの点集合の最大共通部分点集合を求めるランダマイズド・アルゴリズム
- 二次元配列間の距離について
- タンパク質立体構造の折れ線による近似とその構造マッチングへの応用
- 可変長ギャップ付き文字列に対する近似マッチング・アルゴリズム
- タンパク質立体構造に対する部分構造検索およびアラインメント・アルゴリズム
- 高次元点集合の合同性判定について
- Don't Care記号つき文字列に対する近似マッチング・アルゴリズム
- 複数の点集合の最大共通部分集合の近似可能性について