內容簡介

本書專注於一個相當重要且具有深遠影響力的幾何結構──沃羅諾伊圖形（Voronoi Diagram），以及它的幾何對偶，德勞內三角分割（Delaunay triangulation）。

書中徹底闡述沃羅諾伊圖形和德勞內三角分割的結構特性，以及因空間、影響力界定方式之不同，所獲致之沃羅諾伊圖形的各種變型，提供建構該圖形的各種演算法，並描述其在各科學領域的應用；也觸及很多個別的應用及一些替代解題方案。亦討論了演算法實作相關的議題，提出一些重要但尚未解決與亟待解決的問題。

本書為計算幾何學領域中沃羅諾伊圖形相關的文獻，提供了一個完整、貼切的現狀描述，足以讓數學、電腦科學、以及自然與經濟科學等領域的研究學者、教師、研究生，以及具有強烈企圖心，亟欲尋找替代解題方案的工程師們從中得到啟發。

作者簡介

作者／

Franz Aurenhammer
奧地地格拉茨科技大學理論計算機科學系教授

Rolf Klein
德國波昂大學計算機科學研究所教授

Der-Tsai Lee（李德財）
中央研究院資訊科學研究所客座講座

譯者／

李德財
美國伊利諾大學香檳分校電腦科學博士，現為中央研究院資訊科學研究所客座講座、國立台灣大學資工系合聘之特聘研究講座教授、國立中興大學資工系特聘講座教授。曾發表近200篇學術論文，並擔任國際重要期刊編輯委員。獲頒Fellow of IEEE（1992）、Fellow of ACM（1997）、中研院院士（2004）及世界科學院院士（TWAS）（2008）。

劉智弘
台灣大學資訊工程學士和電子工程博士，現為瑞士蘇黎世聯邦理工學院資深博士後研究員。2012年獲得德國亞歷山大宏博基金會（Alexander von Humboldt Foundation）博士後研究獎學金，在德國波昂大學從事計算幾何領域，沃羅諾伊圖形相關的研究，至今發表了十多篇相關論文。

內容目錄

第1章 序論
第2章 基本性質
2.1 沃羅諾伊圖形
2.2 德勞內三角分割
第3章 基本演算法
3.1 下界
3.2 遞增建構法
3.3 分治法
3.4 平面掃視
3.5 提升至三維空間
第4章 進階性質
4.1 沃羅諾伊圖形的特質
4.2 德勞內三角分割的最佳化性質
第5章 廣泛化的址
5.1 線段址沃羅諾伊圖形
5.2 凸多邊形
5.3 直線骨架
5.4 受限的德勞內和相關結構
5.5 曲線物件的沃羅諾伊圖形
第6章 高維空間
6.1 三維空間的沃羅諾伊圖形和德勞內鑲嵌
6.2 力量圖形
6.3 正規單純複合形
6.4 分割定理
6.5 高階沃羅諾伊圖形
6.6 三維空間之中軸
第7章 廣義的空間和距離
7.1 廣泛化的空間
7.2 凸性距離函數
7.3 良好的度量
7.4 加權的距離函數
7.5 抽象的沃羅諾伊圖形
7.6 時間距離
第8章 更多應用和相關結構
8.1 距離問題
8.2 德勞內三角分割的子圖
8.3 德勞內三角分割的母圖
8.4 幾何叢集
8.5 運動規劃
第9章 五花八門
9.1 變動址的沃羅諾伊圖形
9.2 沃羅諾伊區域配置
9.3 區圖形與相關結構
9.4 圖上的鄰近結構
第10章 高維空間的替代方案
10.1 指數大小的下界
10.2 嵌入低維空間
10.3 好的隔離對之分解
10.4 再訪郵局問題
10.5 抽象單純複合形
第11章 結論
11.1 約略涵蓋的主題
11.2 實作的議題
11.3 一些未解問題
參考文獻
索引
英文索引
中文索引