情報科学コース『数理科学特論』ならびに情報科学科３年『応用幾何学』のページ

この講義ではかつて金子研の卒研・院研のテーマとしても取り上げられたこと がある，計算幾何の基本を取り上げます．主に 下記の本の解説とプログラミングの指導を行います． 主な内容は，凸包の計算, 線分交又, 平面の多角形分割, 美術館問題の解法, 領域探索と Kd 木, ボロノイ図, ドロネー３角形分割, ロボットモーションプ ラニングなどです．

M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf 著
『Computational Geometry』, 2nd Ed., Springer, 2000.
(日本語訳もあります．)

• １０月６日(月)：第１回　凸包の計算．
  第１章の内容を紹介します．計算幾何を概観した後，凸包の計算法を説明し， プログラムを動かしてみます．
  cpgeo1.pdf第１回講義のプレゼン
• １０月１３日(月)：祝日です．
• １０月２０日(月)：第２回　線分交又．
  第２章の前半の内容である，多くの線分の交点を能率的に計算する 方法を紹介しました．
  cpgeo2.pdf第２回講義のプレゼン.
• １０月２７日(月)：第３回　面分交又．
  第２章の後半の内容である，二つの地図 (平面の多角形分割) の 重ね合わせを計算する方法を紹介しました．
  cpgeo3.pdf第３回講義のプレゼン.
• １１月３日(月)：祝日です．ほんと，休み多いね．(^^;
• １１月１０日(月)：第４回　三角形分割．
  第３章の解説に入り，多角形の３角形分割を用いた美術館問題の解を紹介し， ３角形分割の準備として，多角形の単調多角形への分割アルゴリズムを 解説しました．
  cpgeo4.pdf第４回講義のプレゼン (11.16.22:05 修正版).
• １１月１７日(月)：第５回　三角形分割から半平面交叉へ．
  第３章の残り，単調多角形の３角形分割の話をした後，第４章に入り， 鋳型から成型物を取り出す方向の探索手段として，半平面の族の共通部分とし て定まる凸多角形の決定アルゴリズムを紹介しました．
  cpgeo5.pdf第５回講義のプレゼン (11.18.8:40 修 正版).
  一晩経ったらプッシュの仕方に勘違いをしたことに気づいたので訂正します． ３年前のレジュメの方が正しかったようです． (ちゃんと書いておかないと忘れますね (^^;)
• １１月２４日(月)：祝日です．
• １２月１日(月)：第６回　線型計画法．
  半平面交叉の応用として２変数の線型計画法の解法を紹介しました．
  cpgeo6.pdf第６回講義のプレゼン.
• １２月８日(月)：第７回　Kd 木．
  最初に高次元の線型計画法を紹介し，次いで 平衡２分木の復習をした後，平面の領域探索のための Kd 木の解説をしました．
  cpgeo7.pdf第７回講義のプレゼン.
  途中でいろいろ首をかしげたところは，まだ検討していませんが， 復習用にとりあえず，ミスプリだけ訂正したものをアップします．
• １２月１５日(月)：第８回　領域探索の続き．
  前回構築した Kd 木を用いた探索法の解説をし，別の２次元領域木を 用いたアルゴリズムも紹介しました．
  cpgeo8.pdf第８回講義のプレゼン.
• １２月１９日(金)(振替月曜)：休講　
  折角増やしてくれた月曜ですが，諸般の事情により予習が追いつかないので お休みします. (^^;
• １２月２２日(月)：第９回　点の位置特定
  平面の多角形分割が与えられたとき，入力点がそのどれに属するかを 効率良く決定するためのデータ構造とアルゴリズムを解説します．
  cpgeo9.pdf第９回講義のプレゼン.
• １月８日(木)(振替月曜)：第１０回　ロボットモーション立案
  台形地図の応用として，障害物を避けてロボットを目的の場所に移動 させる経路の計算法を紹介しました． cpgeoa.pdf第１０回講義のプレゼン.
• １月１２日(月)：祝日です．
• １月１９日(月)：第１１回　ボロノイ図
  与えられた点集合の支配領域を与えるボロノイ図の基本的知識および， 作成アルゴリズムを解説します． cpgeob.pdf第１１回講義のプレゼン.
• １月２６日(月)：第１２回　ドロネー３角形分割
  ボロノイ図の双対として得られるドロネー３角形分割の話をしました． cpgeoc.pdf第１２回講義のプレゼン.
• ２月２日(月)：休講
  これで本講義はおしまいです．単位の欲しい人は，今まで解説したもののどれ かについて，プログラミングをやってみてください．プログラミングが苦手の 人は，計算幾何の面白い問題や，応用でも考えて書いてください．

---

講義科目の紹介メニューに戻る.