計(jì)算幾何

《計(jì)算幾何:算法與應(yīng)用》(第2版)的前4章對幾何算法進(jìn)行了討論，包括幾何求交、三角剖分、線性規(guī)劃等，其中涉及的隨機(jī)算法也是《計(jì)算幾何:算法與應(yīng)用》(第2版)的一個(gè)鮮明特點(diǎn)。第5章至第10章介紹了多種幾何結(jié)構(gòu)，包括幾何查找、kd樹、區(qū)域樹、梯形圖、Voronoi圖、排列、Delaunay三角剖分、區(qū)間樹、優(yōu)先查找樹以及線段樹等。第11章至第16章結(jié)合實(shí)際問題，繼續(xù)討論了若干幾何算法及其數(shù)據(jù)結(jié)構(gòu)，包括高維凸包、空間二分及BSP樹、運(yùn)動(dòng)規(guī)劃、網(wǎng)格生成及四叉樹、最短路徑查找及可見性圖、單純性區(qū)域查找及劃分樹和切分樹等，這些也是對前十章內(nèi)容的進(jìn)一步深化。