授業科目名 | 計算幾何学 |
---|---|
履修期 春 2単位 履修基準年度 3年 |
授業目的 |
---|
幾何学データ処理の基本的なアルゴリズムを学び,それを通してアルゴリズムの設計と解析の基本と,代表的なアルゴリズム設計のパラダイムを習得する. |
到達目標 |
アルゴリズムのパラダイムとして,二分探索,分割統治,逐次添加などの手法を理解し,またそれらの評価法を習得している. |
授業計画 | |||||
---|---|---|---|---|---|
第1回 | 計算幾何学の概観 | ||||
第2回 | 線分交差の判定と,線分交差アルゴリズム | ||||
第3回 | 線分交差の復習と,疑似コードの作り方 | ||||
第4回 | アルゴリズムの解析と計算複雑度 | ||||
第5回 | 凸包のアルゴリズム(1) | ||||
第6回 | 凸包のアルゴリズム(2) | ||||
第7回 | 多角形の面積と三角形分割 | ||||
第8回 | 三角形分割とその応用 | ||||
第9回 | ボロノイ図とドローネ三角形分割 | ||||
第10回 | ドローネ三角形分割とその応用 | ||||
第11回 | ボロノイ図構築アルゴリズム(1) | ||||
第12回 | ボロノイ図構築アルゴリズム(2) | ||||
第13回 | 計算幾何学のその他のトピック(1) | ||||
第14回 | 計算幾何学のその他のトピック(2) |