計算幾何学

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