科目ナンバー

SE-IG3-8C32

履修条件・関連科目等

　「C プログラミング初級」、「C プログラミング初級演習」、「C プログラミング中級演習」、「数理情報学1、2」で学んだ知識をもとに授業を行なう。

授業で使用する言語

日本語

授業で使用する言語（その他の言語）

授業の概要

　計算幾何学では、様々な応用分野に現れる大量の幾何情報をコンピュータで扱うための概念やデータ構造、アルゴリズムを学ぶ。地理情報処理やコンピュータグラフィックス、CAD、パターン認識などでは大量の幾何図形データを高速に処理しなければならない。そのための基礎となる幾何図形問題の計算機上での解法を学習する。

科目目的

　この科目は、映像情報領域の選択科目として位置づけられている。データ構造やアルゴリズムやプログラミングに関して学習した知識を応用して、現実の社会で現れる多くの幾何情報の処理のために必要な能力を身に着けることを目標としている。実際の問題に取り組むために何をすべきかを学ぶ。

到達目標

　多くの種類のアルゴリズムやデータ構造を学ぶことによって、解かなければならない現実の問題を解決する場合に、適切なデータ構造やアルゴリズムの選択をしたり、既存のものを組み合わせて新しいものを開発したりすることが可能になる。特にコンピュータで図形を扱うときに必要となるデータ構造やアルゴリズムについて学び、それを実際に利用できる能力を身に着けることを目標とする。

授業計画と内容

　具体的な例を用いて実際に問題を解いていきながら、アルゴリズムを理解し、幾何的図形を解くプログラムを組む際の問題点をはっきりさせる。授業時間内に適宜演習も行う。

第 1回　計算幾何学とは何か、代表的な問題
第 2回　凸包構成（２次元のアルゴリズム）
第 3回　線分の交差判定と列挙
第 4回　多角形を表現するデータ構造
第 5回　多角形の三角形分割
第 6回　点集合に対する三角形分割
第 7回　Delaunay三角形分割とVoronoi図
第 8回　アレンジメント
第 9回　アレンジメントの応用
第10回　線形計画問題の基本概念
第11回　線形計画問題の幾何学的解法
第12回　直交領域探索（ヒープ探索木）
第13回　点位置決定問題
第14回　まとめと応用

授業時間外の学修の内容

その他

授業時間外の学修の内容（その他の内容等）

授業時間内に示した例題や演習問題に取りくみ、アルゴリズムの動作を確認しておくように心がける。
レポート課題は期日までに作成し、必ず提出すること。

授業時間外の学修に必要な時間数／週

・毎週１回の授業が半期（前期または後期）または通年で完結するもの。１週間あたり４時間の学修を基本とします。
・毎週２回の授業が半期（前期または後期）で完結するもの。１週間あたり８時間の学修を基本とします。

成績評価の方法・基準

成績評価の方法・基準（備考）

課題や試験のフィードバック方法

授業時間内で講評・解説の時間を設ける

課題や試験のフィードバック方法（その他の内容等）

アクティブ・ラーニングの実施内容

その他

アクティブ・ラーニングの実施内容（その他の内容等）

グループディスカッションが可能であれば実施する。

授業におけるICTの活用方法

その他

授業におけるICTの活用方法（その他の内容等）

必要に応じて，Webexミーティング，Google共有ドライブ，Googleクラスルーム等コミュニケーションツールを用いて双方向型の学び及び自主学習支援を実施する．具体的にはその都度指示する．

実務経験のある教員による授業

いいえ

【実務経験有の場合】実務経験の内容

【実務経験有の場合】実務経験に関連する授業内容

テキスト・参考文献等

資料を配布する．
参考書：今井　浩、今井桂子著　「計算幾何学」（共立出版　2,987円）
　　　　浅野哲夫著　「計算幾何学」（朝倉書店　3,914円）

その他特記事項

参考URL