I481F 計算幾何学特論

このページは2014年度のI481F計算幾何学特論の補足ページです． 担当は上原隆平です．

サポート情報

一般的な情報

• シラバス
• 講義時間: 9:20〜12:30
• テキスト: 配布資料をWebで公開
• 参考図書:
  • 「アルゴリズム・サイエンス：入口からの超入門」浅野哲夫，共立出版，2007年．
  • 「コンピュータ・ジオメトリ」M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf著， 浅野哲夫訳，近代科学社，1999年．

教室での授業を録画したビデオ

大学内のみ視聴可能で，Windows 上の IE のみ対応しているようです． 視聴方法|ログイン

講義予定と，講義で使用したPowerPointのPDFファイル

• 11月02日(日) 計算幾何学：歴史的背景から応用まで
• 11月15日(土) 凸多角形に関する問題
• 11月16日(日) 凸包
• 11月29日(土) 幾何的データ構造
• 11月30日(日) 平面操作法
  [補足]途中で話した計算誤差について，後でいろいろと調べてみたところ， 京都産業大学・理学部・数理科学科の 山田修司先生のWebページに コンパクトな良い解説をみつけました．参考にして下さい． 上原の作った円周率πの近似値を求めるプログラムを実行した結果は以下の通りです．

  uehara@water% ./calcpai 100000
  正確な値:	3.1415826535897198
  方法A:		3.1415855884552002
  方法B:		3.1415719985961914
  方法Aの逆順:	3.1415827274322510
  方法Bの逆順:	3.1415901184082031
  uehara@water% ./calcpai 10000000
  正確な値:	3.1415925535897915
  方法A:		3.1415967941284180
  方法B:		2.4503612518310547
  方法Aの逆順:	3.1415925025939941
  方法Bの逆順:	3.1416091918945312

  それぞれの方法の内容はソースを読めばわかると思います．方法Bはひどい…．
• 12月13日(土) ボロノイ図とドローネ三角形分割
  ボロノイ図(Power Diagram)の活用例：ピラミッド折り問題の多項式時間解法
• 12月14日(日) 最小包含円問題
  計算折り紙の話：複数の箱が折れる展開図
• 12月21日(日) 試験(11:00-12:30)：A4一枚持込み可．持込んだ紙は回収します．

その他のPDFファイル

• 11/02(Sun): 配布資料
• 11/02(Sun): 浅野先生の過去問2012年度
• 11/16(Sun): レポート1
• 11/29(Sat): レポート1の解答と解説
• 11/30(Sun): レポート2
• 12/13(Sat): レポート2の解答と解説

その他

• 2014/12/24: 試験の採点終わりました．詳細を知りたい人はメールで連絡下さい．
• 2014/12/14: 試験方法のオプションは，A4用紙を一枚のみ持込みありとします． 紙は最後に回収して，場合によってはボーナス点を加算します． ボーナス点は，あるとしたらいつでも加点で，減点はしません．
• 2014/12/13: 試験方法のオプション（持込み無し/A4を一枚のみ(回収/非回収)/持込みあり）を説明しました．14日に試験方法を決定します．
• 2014/11/29: レポート1は5点満点としていましたが，間違いでした．10点満点に変更します．
• 2014/10/30: ページ公開．

Last modified: Tue Oct 26 13:24:08 JST 2010 by R.Uehara (uehara@jaist.ac.jp)