計(jì)算幾何

內(nèi)容概要

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

作者簡(jiǎn)介

周培德：1941年生，湖北省武穴市人。1956年畢業(yè)于武漢大學(xué)數(shù)學(xué)系。任北京理工大學(xué)計(jì)算機(jī)系教授。2001年9月退休。長(zhǎng)期擔(dān)任本科生"算法設(shè)計(jì)與分析"及研究生"計(jì)算理論"等課程的教學(xué)工作。主要精力集中于計(jì)算機(jī)算法分析與設(shè)計(jì)、計(jì)算幾何等方面的研究。以個(gè)人名義在多種學(xué)術(shù)刊物和全國(guó)學(xué)術(shù)交流會(huì)上發(fā)表論文60篇，出版學(xué)術(shù)專(zhuān)著一部、全國(guó)統(tǒng)編高等學(xué)校教材一部、校"九五"規(guī)劃研究生教材一部、內(nèi)部教材八部。主要論著有《計(jì)算幾何--算法分析與設(shè)計(jì)》、《算法設(shè)計(jì)與分析》、《計(jì)算中的基本理論與方法》。代表性論文有《求解K-中心問(wèn)題的快速算法》、《平面散亂點(diǎn)線(xiàn)集三角剖分的算法》、《平面線(xiàn)段集三角剖分的算法》、《連接不相交線(xiàn)段成簡(jiǎn)單多邊形的算法》等?！端惴ㄔO(shè)計(jì)與分析》獲第三屆全國(guó)普通高校部級(jí)優(yōu)秀教材一等獎(jiǎng)。退休以來(lái)，專(zhuān)心從事計(jì)算幾何及其應(yīng)用領(lǐng)域的研究工作，為6個(gè)課題組，公司設(shè)計(jì)了20來(lái)個(gè)算法，在多種期刊上發(fā)表學(xué)術(shù)論文20來(lái)篇，提出一批新的問(wèn)題及解決相應(yīng)問(wèn)題的算法。

書(shū)籍目錄

第0章  預(yù)備知識(shí)
  0．1  算法與數(shù)據(jù)結(jié)構(gòu)
  0．1．1  算法
  0．1．2  數(shù)據(jù)結(jié)構(gòu)
  0．2  相關(guān)的幾何知識(shí)
  0．2．1  基本定義
  0．2．2  線(xiàn)性變換群下的不變量
  0．2．3  幾何對(duì)偶性
  0．3  計(jì)算模型
第1章  幾何查找(檢索)
  1．1  點(diǎn)定位問(wèn)題
  1．1．1  點(diǎn)□是否在多邊形P內(nèi)
  1．1．2  確定點(diǎn)□在平面剖分中的位置
  1．1．3  Z□算法(判定點(diǎn)q在哪個(gè)三角形的算法)
  1．2  判定點(diǎn)集是否在多邊形內(nèi)
  1．3  平面網(wǎng)絡(luò)的處理與點(diǎn)q的定位
  1．4  平面上鏈的處理與點(diǎn)q的定位
  1．5  平面上線(xiàn)段的處理與點(diǎn)q的定位
  1．6  判定點(diǎn)是否在多邊形內(nèi)部的新算法
第2章  多邊形
  2．1  凸多邊形
  2．2  簡(jiǎn)單多邊形
  2．3  多邊形的三角剖分
  2．4  多邊形的凸劃分
  2．5  對(duì)多邊形鏈的監(jiān)視
  2．6  線(xiàn)段劃分多邊形
  2．7  凸多邊形的內(nèi)接最大三角形及外切最小三角形
第3章  凸殼及其應(yīng)用
  3．1  凸殼的基本概念
  3．2  計(jì)算平面點(diǎn)集凸殼的算法
  3．3  計(jì)算平面多邊形頂點(diǎn)凸殼的算法
  3．4  計(jì)算平面多邊形鏈頂點(diǎn)凸殼的算法
  3．4．1  概念、算法思想與描述
  3．4．2  解釋與時(shí)間復(fù)雜性
  3．5  計(jì)算平面線(xiàn)段集凸殼的算法
  3．6  計(jì)算三維空間點(diǎn)集凸殼的算法
  3．6．1  基本概念
  3．6．2  Z粥算法(三維凸殼)
  3．7  時(shí)間復(fù)雜性低于下界O(nlogn)的凸殼算法
  3．8  凸殼的應(yīng)用
  3．8．1  確定任意多邊形的凸、凹頂點(diǎn)
  3．8．2  利用凸殼求解貨郎擔(dān)問(wèn)題
  3．8．3  凸多邊形直徑
  3．8．4  連接兩個(gè)多邊形成一條回路
第4章  Voronoi圖、三角剖分及其應(yīng)用
  4．1  Voronoi圖的基本概念
  4．2  構(gòu)造Voronoi圖的算法
  4．2．1  z□算法(計(jì)算平面點(diǎn)集的Voronoi圖)
  4．2．2  構(gòu)造最遠(yuǎn)點(diǎn)意義下Voronoi圖的算法
  4．3  平面點(diǎn)集的三角剖分
  4．3．1  Delaunay三角剖分與多邊形內(nèi)部點(diǎn)集的三角剖分
  4．3．2  平面點(diǎn)集三角剖分的算法
  4．4  平面線(xiàn)段集的三角剖分
  4．5  平面點(diǎn)線(xiàn)集的三角剖分
  4．6  平面點(diǎn)集的偽三角剖分
  4．7  偽三角形的產(chǎn)生
  4．8  三角剖分的表示
  4．9  推廣及應(yīng)用
  4．9．1  最近鄰近
  4．9．2  最大化最小角的三角剖分
  4．9．3  最大空?qǐng)A
  4．9．4  最小生成樹(shù)
  4．9．5  貨郎擔(dān)問(wèn)題
  4．9．6  中軸
  4．9．7  Voronoi圖與凸殼的關(guān)系
  4．9．8  Voronoi圖的推廣
  4．9．9  有約束的Voronoi圖
  4．9．10  線(xiàn)段集的Voronoi圖
  4．9．11  關(guān)聯(lián)于多邊形的Voronoi圖
  4．9．12  點(diǎn)線(xiàn)集的Voronoi圖
  4．9．13  點(diǎn)、水平、垂直正交線(xiàn)段集的Voronoi圖
  4．9．14  幾何數(shù)據(jù)壓縮
  4．9．15  車(chē)輛定位導(dǎo)航系統(tǒng)的新定位算法
  4．9．16  調(diào)色
  4．9．17  點(diǎn)集增(刪)點(diǎn)之后的三角剖分
第5章  交與并及其應(yīng)用
  5．1  線(xiàn)段交的算法
  5．2  多邊形的交
  5．2．1  凸多邊形交的算法
  5．2．2  星形多邊形交的算法
  5．2．3  任意簡(jiǎn)單多邊形交的算法
  5．3  半平面的交及其應(yīng)用
  5．3．1  半平面的交
  5．3．2  兩個(gè)變量的線(xiàn)性規(guī)劃
  5．4  多邊形的并
  5．5  凸多面體的交
  5．6  應(yīng)用
  5．6．1  地圖匹配
  5．6．2  地圖數(shù)據(jù)的處理
  5．6．3  線(xiàn)段與凸多面體面的交
  5．6．4  與線(xiàn)段集中線(xiàn)段均相交的直線(xiàn)及其存在區(qū)域
  5．6．5  特定射線(xiàn)詢(xún)問(wèn)
第6章  多邊形的獲取及相關(guān)問(wèn)題
  6．1  連接不相交線(xiàn)段成簡(jiǎn)單多邊形(鏈)
  6．2  紅外圖像邊緣提取
  6．3  提取可見(jiàn)光圖像的邊緣
  6．4  圖像邊界點(diǎn)行排列轉(zhuǎn)換為順序排列
  6．5  數(shù)字圖像中目標(biāo)邊界的多邊形表示
  6．6  包含密集點(diǎn)、線(xiàn)集多邊形的獲取
  6．7  滿(mǎn)足特定條件的多邊形劃分
  6．8  多邊形與多邊形鏈
  6．9  圓弧、直線(xiàn)段組成的多邊形頂點(diǎn)凸、凹性的確定
  6．10  多邊形放大、縮小及移動(dòng)
  6．11  帶狀多邊形的處理
  6．12  下料問(wèn)題(1)
  6．13  下料問(wèn)題(2)
  6．14  下料問(wèn)題(3)
  6．15  線(xiàn)鋸問(wèn)題
  6．16  多邊形(鏈)的匹配(1)
  6．17  多邊形(鏈)的匹配(2)
  6．18  構(gòu)造凸多邊形
  6．19  具有屬性點(diǎn)集的控制區(qū)域
  6．20  多邊形內(nèi)區(qū)域的劃分及多邊形(點(diǎn)集)中心點(diǎn)的確定
  6．21  滿(mǎn)足一定條件的多邊形劃分
  6．22  特定條件下凸多邊形的縮小與放大
第7章  幾何體的劃分與等分
  7．1  平面上不同類(lèi)型點(diǎn)集的劃分
  7．2  多邊形內(nèi)不同類(lèi)型點(diǎn)集的等分
  7．3  平面上不同類(lèi)型線(xiàn)段集的劃分
  7．4  平面上不同類(lèi)型線(xiàn)段集的等分
  7．5  平面上不同類(lèi)型點(diǎn)線(xiàn)集的劃分與等分
  7．6  鏈、多邊形的劃分與等分
第8章  路徑與回路
  8．1  最短路徑
  8．1．1  可視圖及其構(gòu)造
  8．1．2  Z□算法(尋求網(wǎng)絡(luò)中任意兩點(diǎn)間最短路徑的算法
  8．1．3  多面體面上任意兩點(diǎn)之間的最短路徑
  8．1．4  貨運(yùn)汽車(chē)調(diào)度及行駛路徑問(wèn)題
  8．2  最短路徑問(wèn)題的變型
  8．3  滿(mǎn)足一定條件的運(yùn)動(dòng)規(guī)劃
  8．4  多邊形內(nèi)點(diǎn)之間的可視圖
  8．5  多邊形內(nèi)任意兩點(diǎn)之間的最短路徑
  8．6  自主車(chē)自動(dòng)定位及確定行車(chē)方向
  8．7  迷宮問(wèn)題
  8．8  棋盤(pán)上的路徑與回路
  8．9  選擇道路及判定道路的通過(guò)能力
  8．10  多邊形內(nèi)中心區(qū)域的確定
第9章  幾何拓?fù)渚W(wǎng)絡(luò)設(shè)計(jì)
  9．1  G(S)問(wèn)題
  9．1．1  最大間隙問(wèn)題(MAX G)
  9．1．2  點(diǎn)集中最大空凸多邊形問(wèn)題及最大空矩形問(wèn)題
  9．1．3  線(xiàn)段集中最大空凸多邊形問(wèn)題
  9．1．4  點(diǎn)線(xiàn)集中最大空凸多邊形問(wèn)題
  9．1．5  最小覆蓋問(wèn)題(MIN C)
  9．1．6  包含平面點(diǎn)集的最小正方形
  9．1．7  子點(diǎn)集包含問(wèn)題
  9．1．8  2-中心問(wèn)題
  9．1．9  k-中心問(wèn)題
  9．1．10  最近對(duì)問(wèn)題(CPP)
  9．1．11  所有最近鄰近問(wèn)題(ANNP)
  9．1．12  郵局問(wèn)題(POFP)  
  9．1．13  尋找具有屬性點(diǎn)集的最近點(diǎn)對(duì)或點(diǎn)團(tuán)
  9．2  G(E)問(wèn)題
  9．2．1  EMST問(wèn)題
  9．2．2  線(xiàn)段集、點(diǎn)線(xiàn)集的最小生成樹(shù)
  9．2．3  直線(xiàn)最小生成樹(shù)及其相關(guān)問(wèn)題
  9．2．4  歐幾里得TSP
  9．2．5  歐幾里得最大生成樹(shù)問(wèn)題(EMXT)
  9．2．6  最小生成網(wǎng)絡(luò)
  9．3  G(S，E)問(wèn)題
  9．3．1  歐幾里得Steiner最小樹(shù)問(wèn)題(ESMT)
  9．3．2  直線(xiàn)Steiner最小樹(shù)問(wèn)題(RSMT)
  9．3．3  求解ESMT問(wèn)題的算法
  9．4  G(□)問(wèn)題
  9．4．1  有障礙物的最大空隙問(wèn)題(MAX G(□))  
  9．4．2  多邊形集中最大空隙問(wèn)題
  9．4．3  具有障礙物的歐幾里得最短路徑問(wèn)題(ESPO)
  9．4．4  求解E3中ESPO問(wèn)題的算法
  9．4．5  具有障礙物的Steiner最小樹(shù)問(wèn)題(ESMTO)
待解決的問(wèn)題
算法一覽
參考文獻(xiàn)
名詞索引

編輯推薦

　　面對(duì)棘手的構(gòu)造性幾何問(wèn)題，怎么辦？　　從本書(shū)中可以找到有效方法，幫助你排憂(yōu)解難！　　《計(jì)算幾何--算法設(shè)計(jì)與分析（第4版）》（作者周培德）系統(tǒng)地介紹了計(jì)算幾何中的基本概念、求解諸多問(wèn)題的算法及復(fù)雜性分析，概括了求解幾何問(wèn)題所特有的許多思想方法、幾何結(jié)構(gòu)與數(shù)據(jù)結(jié)構(gòu)。

圖書(shū)封面

圖書(shū)標(biāo)簽Tags

無(wú)

評(píng)論、評(píng)分、閱讀與下載

---

    計(jì)算幾何 PDF格式下載

---