幾何学アルゴリズムとその応用

概要

論文の詳細を見る
計算機の使用用途の多様化に従い、幾何学データの高速処理は非常に重要な課題になってきている。地図情報処理やVLSIの回路設計に始まり、グラフィクスでの隠面消去や局面上のメッシュの生成、画像からの物体の切り出し、文字などの物体の認識と種別、更には、移動ロボットのコントロールや航空管制など、幾何学データを取り扱う問題は実に多く、また多様である。幾何学データ処理を目的としたアルゴリズム理論である計算機何学が1970年代のなかばに提唱されてから約20年の年月がたっている。応用の多様化に従って、急速に発展し、理論的な深みとともに取り扱う問題の豊富さも目を見張るものがある(文献1、2、3参照)。この講義では計算幾何学の代表的な問題や手法とその応用を幾つかの問題例を用いて出来るだけ判りやすく紹介する。まずは、古典的なデータ構造であるボロノイ図(図1)を用いて、切り抜き問題(図2)、最小木問題(図3)、メッシュ生成(図4)、経路生成(図5)、面積計算問題、最大包含円問題など、様々な問題を解いてみる事により、計算幾何学の典型的な問題解決法を紹介する。つぎに、点集合をデータとして、それを含むような最小基本図形を求める問題を考えよう。基本図形として凸多角形を考えた場合を凸包問題と言い、円や楕円を考えた場合を最小包含円(楕円)問題(図6)と呼ぶ。低次元に特化された線形計画法による高速算法を通して、典型的なランダム・アルゴリズムとその解析を紹介する。最後に、2次元の点集合からなる画像から基本図形を取り出す方法について考える。画像が一本の直線を表している場合に、最小自乗法、repeated median line estimator,最小垂直距離法などの比較を通じて、最近の手法を幾つか紹介する。さらに、画像が多数の直線や二次曲線からなる場合に行なうサンプル法を通じて、計算幾何学で行なうLass-Vegasサンプリングを紹介する予定である。
1995-03-27

幾何学アルゴリズムとその応用

スポンサーリンク

概要

著者

関連論文

スポンサーリンク