[previous page]

---

成績評価 評価・配点方法 成績は、100点満点として評価される。 配点は、プログラミング問題4回＝50点、またはプロジェクト研究1回＝50点、および期末試験1回＝50点。 プログラミング問題（５０％） 計算幾何学に利用されるデータ構造とアルゴリズムを理解した上、プログラムの実装を通じて、学んだ知識を深める。 下記の課題から、毎章最多１つ、得意の４つを選んでプログラムを作成する。 提出期限＝該当章の授業終了後一週間以内 提出先＝wenxi, m5201125, m5201149 第１章 基本概念(Basic Concepts) ２分探索木による検索、挿入、削除を行う関数を作成 データ集合を並び替える五つの方法から二つを選んでプログラムを作成 ２色木又はAVL木の手法を用いて木のバランスを行うプログラムを作成 第２章 線分交差(Line Segment Intersection) ２本ずつ方法と平面走査法を用いて直交線分の交差を求めるプログラムを作成し、両者のパフォーマンスを考察 ２本ずつ方法と平面走査法を用いて任意線分の交差を求めるプログラムを作成し、両者のパフォーマンスを考察 第３章 凸包(Convex Hull) 直接法とGraham走査法による凸包を求めるプログラムを作成、両者のパフォーマンスを考察 包装法と逐次添加法による凸包を求めるプログラムを作成、両者のパフォーマンスを考察 内点消去法による前処理を行い、分割統治法又はQuick法による凸包を求めるプログラムを作成、前処理の有無のパフォーマンスを考察 第４章 ボロノイ図(Voronoi Diagram) 直接法によるボロノイ図を求めるプログラムを作成 逐次添加法によるボロノイ図を求めるプログラムを作成 Fortune走査法によるボロノイ図を求めるプログラムを作成 第５章 ドローネ三角形分割(Delaunay Triangulation) ボロノイ図の双対グラフからドローネ三角形分割を求めるプログラムを作成 不当なフリップ法によるドローネ三角形分割を求めるプログラムを作成 逐次添加法によるドローネ三角形分割を求めるプログラムを作成 プロジェクト研究（５０％） 実社会に存在していて、計算幾何学と関連のある問題を考察し、プロジェクト課題として提起し、色々なリソースから調査活動を展開し、勉強した知識を総合的に駆使して、実際問題解決へのアプローチを研究する。 下記の課題、または自分の考案した課題から１つを選んで４ページ以上の研究レポートを作成する 提出期限＝2017年11月27日 提出先＝wenxi 最近点課題 ★目的： 国民の日常生活と密接する社会インフラの整備状況を調べ、その適切性を検討し、改善策を考え、関連組織に提案する ★作業ステップ： 学校、コンビニ、郵便局、ガソリンスタンドや高速ICなど、いずれ一種類を決め、位置情報を調べる その経緯度情報をx-y直交座標に変換する 提出されたプログラムを用いてボロノイ図を構成する レポートを作成（目的、方法、データ、結果、考察、結論、参考文献など） 参考サイト： 会津若松市郵便局 ヤマト運輸→最寄り店検索→福島県→会津若松市 　　　　 線分交差課題 ★目的： 2つ以上の都市の道路交差点数と交通事故件数の関係を調べ、両者の関連性について検討し、改善策を考え、関連組織に提案する ★作業ステップ： 都市の道路地図を作成する（直線線分で曲がっている道路を近似する） 提出されたプログラムを用いて交差点数を求める 都市の年間交通事故件数を調べる レポートを作成（目的、方法、データ、結果、考察、結論、参考文献など） 参考サイト： 交通事故発生マップ 交通事故発生状況 　　　　 自分の考案した課題 ★目的： 上記提案された課題以外、計算幾何学知識の応用可能な実社会にある問題を、プロジェクト課題として提起し、研究する。 ★作業ステップ： 現実社会に存在している問題を調査する 関連情報・データを収集する 計算幾何学との関連を付け、問題解決を試みる レポートを作成（目的、方法、データ、結果、考察、結論、参考文献など） 参考サイト： Computational geometry Geometry in Action 　　　　 　　　　 期末試験（５０％） 基本概念についての理解度を検証する 2017/11/30, 16:30-18:00 (5th period), M6 採点結果 2017年度計算幾何学 Created by Computational Geometry Team, 2017