計算幾何

內(nèi)容概要

　　本書系統(tǒng)地介紹了計算幾何中的基本概念、求解諸多問題的算法及復(fù)雜性分析，概括了求解幾何問題所特有的許多思想方法、幾何結(jié)構(gòu)與數(shù)據(jù)結(jié)構(gòu)。全書共分11章，包括：預(yù)備知識，幾何查找（檢索），多邊形，凸殼及其應(yīng)用，Voronoi圖、三角剖分及其應(yīng)用，交與并及其應(yīng)用，多邊形的獲取及相關(guān)問題，幾何體的劃分與等分、算法的運動規(guī)劃、幾何拓?fù)渚W(wǎng)絡(luò)設(shè)計、隨機幾何算法與并行幾何算法等。　　本書可作為高等院校計算機專業(yè)研究生或本科高年級學(xué)生的教材，也可作為相關(guān)專業(yè)科技工作者的參考書。

作者簡介

　　周培德，1941年，湖北省武穴市人。1965年畢業(yè)于武漢大學(xué)數(shù)學(xué)系。任北京理工大學(xué)計算機系教授。
　　主要成果為：個人獨立發(fā)明計算機算法160多個，發(fā)表學(xué)術(shù)論文60余篇，出版學(xué)術(shù)專著3部，研究生教材兩部。

書籍目錄

第0章  預(yù)備知識  0.1  算法與數(shù)據(jù)結(jié)構(gòu)    0.1.1  算法    0.1.2  數(shù)據(jù)結(jié)構(gòu)  0.2  相關(guān)的幾何知識    0.2.1  基本定義    0.2.2  線性變換群下的不變量    0.2.3  幾何對偶性  0.3  計算模型第1章  幾何查找（檢索）  1.1點  定位問題    1.1.1  點q是否在多邊形P內(nèi)    1.1.2  確定點q在平面剖分中的位置    1.1.3  Z1-3算法（判定點q在哪個三角形的算法）  1.2  范圍查找問題    1.2.1  多維二叉樹（k-D樹）的方法    1.2.2  直接存取方法    1.2.3  范圍樹方法  1.3  判定點集是否在多邊形內(nèi)  1.4  平面網(wǎng)絡(luò)的處理與點q的定位  1.5  平面上鏈的處理與點q的定位  1.6  平面上線段的處理與點q的定位第2章  多邊形  2.1  凸多邊形  2.2  簡單多邊形  2.3  多邊形的三角剖分  2.4  多邊形的凸劃分第3章  凸殼及其應(yīng)用  3.1　凸殼的基本概念  ……第4章  Voronoi圖、三角剖分及其應(yīng)用第5章  交與并及其應(yīng)用第6章  多邊形的獲取及相關(guān)問題第7章  幾何體的劃分與等分第8章  算法的運動規(guī)劃第9章  幾何拓?fù)渚W(wǎng)絡(luò)設(shè)計第10章  隨機幾何算法與并行幾何算法待解決的問題算法一覽參考文獻(xiàn)名詞索引

章節(jié)摘錄

第0章　預(yù)備知識0.1　算法與數(shù)據(jù)結(jié)構(gòu)0.1.1 算法眾所周知，算法是求解一個問題類的無二義性的有窮過程。這里的過程是指求解問題執(zhí)行的一步一步動作的集合，每一步動作只需要有限的存儲單元和有限的操作時間。另外，如果詳細(xì)說明一臺典型的計算機以及與這種計算機通信的語言，那么凡用這種語言編寫的、可以在給定的計算機上執(zhí)行的過程便稱為算法。隨機存取機器（RAM）、圖靈機等可以作為典型的計算機，擬ALGOL語言作為描述算法而非執(zhí)行的語言。應(yīng)該指出，算法不等于程序，因此描述算法的方式將是多種形式的，如在擬ALGOL語言的描述中可以使用數(shù)學(xué)記號和自然語言。為了把算法轉(zhuǎn)換成上機程序，還需要進(jìn)行編程工作。算法的復(fù)雜性包括算法的時間復(fù)雜性和算法的空間復(fù)雜性。為了說明復(fù)雜性的概念，先介紹問題規(guī)模的概念。用一個與問題相關(guān)的整數(shù)量來衡量問題的大小，該整數(shù)量表示輸入數(shù)據(jù)量的尺度，稱為問題的規(guī)模。比如，行列式的規(guī)?？梢杂闷潆A數(shù)n來表示，圖問題的規(guī)?？梢杂闷溥厰?shù)或頂點數(shù)來表示，等等。利用某算法處理一個問題規(guī)模為n的輸入所需要的時間，稱為該算法的時間復(fù)雜性。它顯然是n的函數(shù)，記為T（n）。類似地，可以定義算法的空間復(fù)雜性S（n）。下面主要討論算法的時間復(fù)雜性。由于一般不需要知道精確的時間耗費，只要知道時間耗費的增長率大體在什么范圍內(nèi)即可，因此我們引入算法復(fù)雜性階的概念。

編輯推薦

《計算幾何:算法設(shè)計與分析(第3版)》可作為高等院校計算機專業(yè)研究生或本科高年級學(xué)生的教材，也可作為相關(guān)專業(yè)科技工作者的參考書。

圖書封面

圖書標(biāo)簽Tags

無

評論、評分、閱讀與下載

---

    計算幾何 PDF格式下載

---