Computational Geometry
計算幾何学
担当：磯 直行
秋学期月曜日１限（メディア科学科３年生）
「計算幾何学」の講義についての情報がかかれています．
目的とねらい
視覚的には簡単な問題でも計算機にとっては非常に難しいという場
合が多い．計算幾何学は，幾何学に計算の複雑さの理論を導入し，
幾何学的な問題に対する効率の良いアルゴリズムを開発，またはそ
の問題の難しさを解析する計算機科学の一分野である．また，計算
幾何学は地理情報処理，ＶＬＳＩのＣＡＤ，グラフィックスなど幅
広い分野に応用されている．本講義では，計算幾何学の基本的技法
について説明した後，凸包問題，多角形領域の基本図形への分解，
可視性問題などの基本問題に関する効率の良い処理手法について学
ぶ．
授業項目
- 計算幾何学とは？
- 基本データ構造
- 区間データの扱い
- 凸多角形に関する問題
- 分割統治法
- 動的計画法
- 平面走査法
- 直線のアレンジメント
- 双対変換
- 枝刈探索法
- 凸包問題
- 多角形領域の基本図形への分解
- 可視性問題
- 可視グラフの構成
- プログラミング演習
教科書
ドバーグ他：コンピュータ・ジオメトリ，近代科学社
参考書
- 浅野哲夫: 計算幾何学、朝倉書店
- 茨木：Ｃによるアルゴリズムとデータ構造，昭晃堂
- F.P.プレパラータ，M.I.シェーモス(浅野孝夫・浅野哲夫訳):
計算幾何学入門、総研出版
- 杉原: FORTRAN計算幾何プログラミング、岩波書店
成績評価方法
レポート，定期試験（持ち込み不可）
履修上の注意
「アルゴリズムとデータ構造」の知識が必須である．
2000.11.09.
[email protected]