計算幾何

先修課程及準備工作

  1. 演算法, 特別是 big-O 觀念與術語
  2. 複習一點數學: 幾何觀念 與 拓撲基本術語
  3. 取得 perl/Tk, 並安裝 algotutor
  4. 科學運算需要高度的穩定性, 經常當機 (或中毒) 的作業系統與工具軟體並不適用, 所以從事科學運算的學者多在 *nix 系統上, 使用 gnu 環境 裡面的相關工具來研發軟體。 本課程當中可能會需要上網下載計算幾何相關軟體並自行編譯, 因此最好在自己的電腦上安裝 Linux 或 *BSD, 或者最起碼也應該在你常用的作業系統上安裝 cygwin 之類的 gnu 模擬環境。

課本/參考書/參考資料

  1. F. Preparata and M. Shamos. Computational Geometry: An Introduction Springer-Verlag, NY, 1985
  2. K. Mulmuley. Computational Geometry: An Introduction through Randomized Algorithms Prentice Hall, 1994 (松瑞代理?)
  3. M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf. Computational Geometry: Algorithms and Applications. 2nd Ed. Springer-Verlag 2000
  4. Dave Mount's Lecture Notes (下載網頁中的 "754 Lecture Notes" pdf 檔)
  5. Jianer Chen's Lecture Notes (下載網頁中的 "geo.pdf" 檔)
  6. geomview 簡介
  7. Stewart Scott Cairns. Introductory Topology
  8. Jeff Erickson 收集的 CG 資源
  9. Guide to Available Mathematical Software
  10. C.G. Links in google
  11. Computational Geometry Algorithms Library

大綱

  1. 一兩個簡單的例子
  2. What is Computational Geometry? (Toussaint)
  3. 作業一: 從 Toussaint 的 "What is Computational Geometry?" 文中提到的眾多應用面裡面挑一個主題 (vision 或 robotics 或 GIS ...) 讀一篇計算幾何在該領域應用的 survey papers, 然後寫一篇報告, 題目為 「計算幾何在 ... 領域的應用實例」。 報告裡面應明確描述至少兩個應用問題。 每個問題應包含 「問題描述」 (用原領域的術語描述), 「幾何描述」 (用計算幾何的方式描述, 最好用一張圖做例子), 「複製度」 (已知的最佳演算法; 實用的演算法; 問題的下限), 「現成軟體」。 報告的總字數請控制在 1000 到 2000 字之間。 David Eppstein 的 Geometry in Action 可能會有幫助。
  4. 特別複習: asymptotic notations
  5. 快速複習: 演算法 (搭配課程進度, 請自行操作 algotutor 練習)
  6. 複習一點數學: 幾何觀念 與 拓撲基本術語
  7. 小考一: 演算法與數學的複習
  8. ... Dave Mount's Lecture Notes (下載網頁中的 "754 Lecture Notes" pdf 檔) ...
  9. Guy Blelloch. Algorithms in the Real World