計算幾何——算法設計與分析（第4版）

內容簡介

本書系統地介紹了計算幾何中的基本概念、求解諸多問題的算法及複雜性分析，概括了求解幾何問題所特有的許多思想方法、幾何結構與數據結構。全書共分10章，包括: 預備知識，幾何查找（檢索）,多邊形,凸殼及其套用,Voronoi圖、三角剖分及其套用，交與並及其套用，多邊形的獲取及相關問題，幾何體的劃分與等分，路徑與迴路，幾何拓撲網路設計等。

本書可作為高等院校計算機、自動化等專業研究生或本科高年級學生的教材或教學參考書,也可供軟體開發人員、相關專業科技工作者參考。

圖書目錄

第0章預備知識

0.1算法與數據結構

0.1.1算法

0.1.2數據結構

0.2相關的幾何知識

0.2.1基本定義

0.2.2線性變換群下的不變數

0.2.3幾何對偶性

0.3計算模型

第1章幾何查找(檢索)

1.1點定位問題

1.1.1點q是否在多邊形P內

1.1.2確定點q在平面剖分中的位置

1.1.3Z1-3算法(判定點q在哪個三角形的

算法)

1.2判定點集是否在多邊形內

1.3平面網路的處理與點q的定位

1.4平面上鏈的處理與點q的定位

1.5平面上線段的處理與點q的定位

1.6判定點是否在多邊形內部的新算法

第2章多邊形

2.1凸多邊形

2.2簡單多邊形

2.3多邊形的三角剖分

2.4多邊形的凸劃分

2.5對多邊形鏈的監視

2.6線段劃分多邊形

2.7凸多邊形的內接最大三角形及外切最小三角形

計算幾何——算法設計與分析

第3章凸殼及其套用

3.1凸殼的基本概念

3.2計算平麵點集凸殼的算法

3.3計算平面多邊形頂點凸殼的算法

3.4計算平面多邊形鏈頂點凸殼的算法

3.4.1概念、算法思想與描述

3.4.2解釋與時間複雜性

3.5計算平面線段集凸殼的算法

3.6計算三維空間點集凸殼的算法

3.6.1基本概念

3.6.2Z3-8算法（三維凸殼）

3.7時間複雜性低於下界O（nlogn）的凸殼算法

3.8凸殼的套用

3.8.1確定任意多邊形的凸、凹頂點

3.8.2利用凸殼求解貨郎擔問題

3.8.3凸多邊形直徑

3.8.4連線兩個多邊形成一條迴路

第4章Voronoi圖、三角剖分及其套用

4.1Voronoi圖的基本概念

4.2構造Voronoi圖的算法

4.2.1Z′4-1算法（計算平麵點集的Voronoi圖）

4.2.2構造最遠點意義下Voronoi圖的算法

4.3平麵點集的三角剖分

4.3.1Delaunay三角剖分與多邊形內部點集的三角剖分

4.3.2平麵點集三角剖分的算法

計算幾何——算法設計與分析（第4版）

基本介紹

內容簡介

圖書目錄

相關詞條

熱門詞條