計算幾何——算法與套用（第2版）

圖書簡介

計算幾何是計算機理論科學的一個重要分支.自20世紀70年代末從算法設計與分析中獨立出來起，不到30年，該學科已經有了巨大的發展，不僅產生了一系列重要的理論成果，也在眾多實際領域中得到了廣泛的套用.　本書的前4章對幾何算法進行了討論，包括幾何求交、三角剖分、線性規劃等，其中涉及的隨機算法也是本書的一個鮮明特點.第5章至第10章介紹了多種幾何結構，包括幾何查找、kd樹、區域樹、梯形圖、Voronoi圖、排列、Delaunay三角剖分、區間樹、優先查找樹以及線段樹等.第11章至第16章結合實際問題，繼續討論了若干幾何算法及其數據結構，包括高維凸包、空間二分及BSP樹、運動規劃、格線生成及四叉樹、最短路徑查找及可見性圖、單純性區域查找及劃分樹和切分樹等，這些也是對前十章內容的進一步深化.
本書不僅內容全面，而且緊扣實際套用，重點突出，既有深入的講解，同時每章都設有“注釋及評論”和“習題”，為讀者更深入的理解提供了可能.因此近年來作為教材一直流行於世界眾多大學校園中.我國在計算幾何方面的研究起步較晚，相信本書的出版能對國內此方面教學工作的開展有所推動.

前言

20世紀70年代末，計算幾何從算法設計與分析中孕育而生.今天，它不僅擁有自己的學術刊物和學術會議，而且形成了一個由眾多活躍的研究人員組成的學術群體，因此已經成長為一個被廣泛認同的學科.該領域作為一個研究學科之所以會取得成功，一方面是由於其涉及的問題及其解答本身所具有的美感，另一方面，也是由於在眾多的套用領域（諸如計算機圖形學、地理信息系統和機器人學等）中，幾何算法都發揮了重要的作用.

解決許多幾何問題的早期算法，要么速度很慢，要么難以理解與實現.隨著近年來一些新的算法技術的發展，此前的很多方法都得到了改進與簡化.在這本教材中，我們力圖使這些現代的算法能夠被更廣泛的讀者理解和接受.本書既是面向計算幾何課程的一本教材，同時也可用於自學.

本書的結構.除“導言”外，每一章都從來自套用領域的某一實際問題入手，這個問題將被轉化為一個純粹的幾何問題，並通過計算幾何所提供的方法得到解決.每一章所討論的，實質上就是對應的幾何問題，以及解決該問題所需要的概念與方法.我們根據所希望覆蓋的計算幾何專題，來選取有關的套用；而就具體的套用領域而言，這些介紹還遠遠不夠全面.引入這些套用的目的，只是為了激發讀者的興趣；而各章本身的目的，並不在於為這些問題提供現成可用的解決方法.雖然如此，我們還是認為，為了有效地解決套用中的幾何問題，計算幾何方面的知識是非常重要的.我們希望本書不僅能夠吸引從事算法研究的學者，而且對套用領域的讀者也同樣有所幫助.

同一幾何問題，可能有多種不同的解決方法，不過，在論述大多數幾何問題時，我們將只給出其中一種.我們通常所選取的，都是最易於理解與實現的方法.我們也十分注意，盡力使本書能夠涵蓋更多的方法，比如分治策略、平面掃描以及隨機算法等.對每個問題可能的種種變型，我們也不打算面面俱到；我們覺得，更重要的是首先對計算幾何中的各個主要問題作一介紹，而不是過於深入地去探究少數專題的細枝末節.

某些章的若干節標有星號.這些節的內容涉及解法的改進與擴展，或者解釋了不同問題之間的相互關聯.就對後續章節的理解而言，它們並不十分重要.

計算幾何——算法與套用（第2版）

基本介紹

圖書簡介

前言

目錄

相關詞條

熱門詞條