計算幾何学
| 授業目的 |
|---|
| 幾何学データ処理の基本的なアルゴリズムを学び，それを通してアルゴリズムの設計と解析の基本と，代表的なアルゴリズム設計のパラダイムを習得する． |
| 到達目標 |
| アルゴリズムのパラダイムとして，二分探索，分割統治，逐次添加などの手法を理解し，またそれらの評価法を習得している． |
| 授業計画 | |
|---|---|
| 第1回 | 線分交差判定のアルゴリズム：アルゴリズムパラダイム 【授業外学修】シラバス追加情報に添付のニュートン（別冊）用の4ページの原稿を読んで，計算幾何学の概観をつかんでください． |
| 第2回 | 線分交差列挙アルゴリズムとデータ構造 |
| 第3回 | 疑似コードの書き方と封筒裏の計算 |
| 第4回 | 凸包とその計算 |
| 第5回 | 凸包の高速アルゴリズム 【授業外学修】疑似コードの作成 |
| 第6回 | 凸多角形の利用： 最遠点対計算と衝突判定 【授業外学修】復習問題 |
| 第7回 | ボロノイ図とその性質 【授業外学修】疑似コードの作成 |
| 第8回 | ボロノイ図の計算アルゴリズム 【授業外学修】復習問題 |
| 第9回 | ボロノイ図の利用：最近傍点探索と物体の骨組 【授業外学修】疑似コードの作成 |
| 第10回 | ドローネ三角形分割とその性質 【授業外学修】復習問題 |
| 第11回 | ドローネグラフの部分グラフたちとグラフスパナ― 【授業外学修】復習問題 |
| 第12回 | 物体の認識と再構築： CRUSTアルゴリズムとアルファ概形 【授業外学修】復習問題 |
| 第13回 | 領域探索とハムサンドイッチ切断 【授業外学修】復習問題 |
| 第14回 | ラムゼー理論とハッピーエンド定理 【授業外学修】復習問題 |
| 第15回 | 点と直線のインシデンスとグラフ描画の交差数 |