Subir Kumar Ghosh Tata Institute of

Fundamental Research，India

Visibility Algorithms

in the Plane

2007, 318pp.

Hardcover

ISBN 9780521875745

S.K.戈希著

一個(gè)人(作為觀察者)容易從某個(gè)環(huán)境中識(shí)別出一個(gè)幾何體的可見(jiàn)部分，但要通過(guò)計(jì)算做到這點(diǎn)，即使高速計(jì)算機(jī)也相當(dāng)耗費(fèi)時(shí)間。由此產(chǎn)生了設(shè)計(jì)合適的算法(稱可視性或直觀性算法)的研究課題。近三十多年來(lái)這項(xiàng)研究的深入發(fā)展，使可視性算法成為計(jì)算幾何領(lǐng)域的一個(gè)重要組成部分。本書(shū)的主題是二維情形可視性問(wèn)題的基本算法，它系統(tǒng)全面地論述了可視性的概念和幾何性質(zhì)，給出各種類型的平面可視性算法。

全書(shū)由8章組成。1.給出背景材料，是全書(shū)的預(yù)備，如可視性概念、多角形與三角剖分、漸近復(fù)雜性等，其余各章分別論述各種特殊的可視性算法，包括點(diǎn)可視性、弱可視性、LR可視性最短路算法、可視性圖與連桿路等，還討論了可視性查詢問(wèn)題，配合正文給出300多個(gè)圖示，并且作為正文的有機(jī)組成穿插一百多個(gè)習(xí)題。

本書(shū)論述清晰，證明詳盡，易于理解，可作為有關(guān)專業(yè)研究生教材，對(duì)于計(jì)算幾何、計(jì)算機(jī)繪圖、機(jī)器人設(shè)計(jì)、算法理論及幾何圖論等領(lǐng)域的科研人員也是有價(jià)值的參考資料。

朱堯辰，研究員

(中國(guó)科學(xué)院應(yīng)用數(shù)學(xué)研究所)

Zhu Yaochen, Professor

(Institute of Applied Mathematics,CAS)