論理回路特論
（岩間）
本年度は以下のように変更されます．
計算幾何学入門
（デビッド・エービス）
内容: 計算幾何学の基本アルゴリズム，凸包，多角形，可視性，交わり，直線配置，ボロノイ図，高次元の計算幾何学
授業計画:
- 入門 （１〜２時間）美術館定理，多角形，三角形分割，可視性
- 直径，凸包 （２〜３時間）直径探索問題，凸包，凸包アルゴリズム，離散幾何学，キャリパー
- 最遠点対問題（１〜２時間）最遠点対の計算および数え上げ
- 最近点対問題（１〜２時間）ボロノイ図，最近点対の計算および数え上げ
- 交わり問題 （２〜３時間）交わり, Radon分割とHellyの定理, 横断線の計算
- 高次元の問題（３〜４時間）凸多面体，頂点列挙アルゴリズム, 逆探索，計算量の上下限, 線形計画問題との関わり
履修条件：アルゴリズムおよび線形代数の基礎知識を有することが望ましい．
テキスト：「計算幾何学・離散幾何学」，D. Avis，今井浩，松永信介， 朝倉書店