授業科目

計算幾何学
Computational Geometry

担当者

准教授 内田 智史
後 火2
助教   奥野 祥二
後 火1

単位

2

到達目標

 本講義の到達目標は、受講生が、①コンピュータを用いて計算幾何学を解くアルゴリズムの基礎について理解し、②それを実現するプログラムをJava言語を用いて、オブジェクト指向の考え方をベースとして記述することができるようになり、③グラハムスキャンなどのアルゴリズムを説明できる能力を身に付けることである。

 また、情報システム創成学科のカリキュラム・ポリシーに従い、計算幾何学の基本的な知識がさまざまな問題の解決に役立つことを体感することにより、 デザイン・ソフトウェア・コンテンツ等の製品価値を生み出す能力を身に付けることを目標とする。

授業内容

 計算幾何学とは、コンピュータを用いて幾何学問題を解くためのさまざまなアルゴリズムを研究する学問である。その成果は、各種のコンピュータグラフィックスシステムなどに活かされ、さらにそれが多くのアミューズメントソフトウェアだけでなく、医療分野や工業製品の製作などにも活かされていることはいうまでもない。本講義では、計算幾何学の分野から、線分の交差判定、凸包の構成、動くボール、弾むボールなどの話題を選び、Java言語で簡単なこれらのプログラムが書けるようになることを目標とする。また、本講座のために、Web教材が開発されており、それを用いて多元的に授業を進める予定である。また、本授業では、計算幾何学の課題を解くプログラムを書くための実習も行う。

授業計画

授業内容はすべてWeb上に公開している。予習として、①各回の該当ページをあらかじめ読んでくること、②出題されている課題に関しては、どのように解いたらよいかを考えておくこと、の2点が不可欠である。また、復習としては、各回の該当ページを読み直し、授業内容を確実に理解したかどうかを確認しておくこと。理解していない場合、あるいはよく分からない項目があった場合については、必ず質問することが必要である。なお、予習・復習合わせて各回あたり約4時間の自己学習を想定している。

授業内容は次のとおりである。

 1.幾何学の簡単な復習(1回)
  初等幾何学について簡単に復習し、本講義の用語や概念を統一する。
 2.計算幾何学とは(1回)
  計算幾何学の全体像を概観する。また、その研究成果が活かされている分野なども紹介する。
  さらにJava言語の概要も学習する。
 3.グラフィックスの描画(3回)
  Javaによるグラフィックスの描画方法について学習し、実際にプログラムを作成する実習を行う。
  その内容は、(1)フレームの表示、(2)グラフィックス命令、(3)グラフィックス演習である。
 4.線分の性質(2回)
  以降の講義の基礎として、線分の持つ数学的な性質について調べる。
  その内容は、(1)線分の性質、(2)線分の方向の判定である。
 5.線分の交差判定(4回)
  任意の2つの線分が交差しているかどうかプログラムで判定する方法について学習する。
  コンピュータグラフィックスではこの処理は非常に利用価値がある(Web教材有り)。
  その内容は、(1)交差判定概要、(2)線分の重なりとその判定プログラム、(3)限界長方形の重複検査、(4)外積による交差判定、(5)Javaプログラム演習である。
 6.凸包の構成(2回)
  ある点集合が凸多角形の内部にあるかどうかを判定するアルゴリズムについて学習する。
  これは多少複雑なアルゴリズムであるが、多くの有益な事項を含んでいる。
  そのアルゴリズムの中でもGrahamスキャンを取り上げる。
  その内容は、(1)Grahamスキャンの概要とGrahamスキャンの計算例、(2)アルゴリズム記述実習である。
 7.総合復習(1回)
  計算幾何学に関連する復習を行う。

授業運営

 1.8割以上出席すること。
 2.課題レポートおよびミニテストを課す。
 3.最終試験を行う。
 4.補講を行うことがある。

評価方法

 最終試験70%、課題レポートおよびミニテスト30%で評価する。

オフィスアワー

 内田:水曜日12:40~13:20、23号館431研究室(内線3738)(研究室23号館431教室にいるときは常時質問可)。
   あるいはs-uchida@jindai.jpまで(常時)。
 奥野:月曜日12:40~13:20、23号館430研究室(内線3737)
   あるいはokuno@kanagawa-u.ac.jpまで(常時)。

使用書

必要な教材はWebLecなどによってインターネット上で配布する。

参考書

T. コルメンら共著、浅野哲夫ら共訳『アルゴリズムイントロダクション[第3巻]精選トピックス』[近代科学社]
 参考書は必ずしも必要ではないが、将来情報系の分野に進みたい方には、ぜひ一読をすすめたい書籍である。

Copyright© 2017 Kanagawa University. All Rights Reserved.