駆け足で読む計算幾何学入門 第１章 はじめに

• 計算幾何学
  • 幾何学的な問題を扱うアルゴリズムの設計と解析の学問。幾何学的な対象は、従来の情報処理方式と異なったアプローチを要することが多く、独特な特徴を備える
• 幾何用語
  • d次元ユークリッド空間
  • 点・直線・平面・線形多様体・多面体
  • 線分
  • 凸領域・凸集合・凸包
  • グラフ
  • 分割・アレンジメント(高次空間での分割)
• 計算量
• データ構造
  • リスト
  • スタックとキュー
  • ヒープ
  • ２分探索木(Wikipediaの記事)
  • 平衡２分探索木
• 多数のデータがあって、該当データを探すとき、データに決まりがなければ、しみつぶしにするしかない
• データに順序があれば、その順序を利用して探索をかける(ソートしたリストを用いた２分探索)
• データに順序があり、該当データを探すだけでなく、データを入れたり出したりするときには、２分探索木を用いる