多面体の合同判定のためのn log nアルゴリズム

スポンサーリンク

概要

論文の詳細を見る
2個の多面体が合同であるか否かを判定する効率のよいアルゴリズムを構成する. これは, 多面体の稜線の数をnとするとき, 計算時間の上限がn log nに比例するものである. また, 3連結平面グラフの同形判定技法を利用しているにもかかわらず, 対象とする多面体の頂点と稜線の作るグラフは3連結である必要も平面グラフである必要もないという著しい一般性をもっている. さらに, 多面体の一部分が別の多面体の一部分と合同であるか否かもn^2に比例した計算時間で判定できることを指摘する. 本稿の成果は, 多眼視などによって得られた立体形状情報から物体の種類を同定したり, 立体形状設計のための計算機支援システムにおいて部品を組み立てる際のはめ合いがうまくいくか否かを判定したりするときに役立つものである.
1982-11-15

著者

関連論文

スポンサーリンク