Computational Geometry: An Introduction Through Randomized Algorithms (Paperback)

Ketan Mulmuley

Computational Geometry: An Introduction Through Randomized Algorithms (Paperback)
  • 出版商: Prentice Hall
  • 出版日期: 1993-06-18
  • 售價: $676
  • 語言: 英文
  • 頁數: 447
  • 裝訂: Paperback
  • ISBN: 0133363635
  • ISBN-13: 9780133363630
  • 相關分類: Algorithms-data-structures

    • 無法訂購

買這商品的人也買了...

相關主題

商品描述

Description:

For beginning graduate-level courses in computational geometry.

This up-to-date and concise introduction to computational geometry — with emphasis on simple randomized methods — is designed for quick, easy access to beginners.

 

Table of Contents:

I. BASICS.

1. Quick-sort and Search.

 

Quick-sort. Another view of quick-sort. Randomized binary trees. Skip lists.

 

2. What Is Computational Geometry?

 

Range queries. Arrangements. Trapezoidal decompositions. Convex polytopes. Voronoi diagrams. Hidden surface removal. Numerical precision and degeneracies. Early deterministic algorithms. Deterministic vs. randomized algorithms. The model of randomness.

 

3. Incremental Algorithms.

 

Trapezoidal decompositions. Convex polytopes. Voronoi diagrams. Configuration spaces. Tail estimates.

 

4. Dynamic Algorithms.

 

trapezoidal decompositions. Voronoi diagrams. History and configuration spaces. Rebuilding history. Deletions in history. Dynamic shuffling.

 

5. Random Sampling.

 

Configuration spaces with bounded valence. Top-down sampling. Bottom-up sampling. Dynamic sampling. Average conflict size. More dynamic algorithms. Range spaces and E-nets. Comparisons.

 

II. APPLICATIONS.

6. Arrangements of Hyperplanes.

 

Incremental construction. Zone Theorem. Canonical triangulations. Point location and ray shooting. Point location and range queries.

 

7. Convex Polytopes.

 

Linear Programming. The number of faces. Incremental construction. The expected structural and conflict change. Dynamic maintenance. Voronoi diagrams. Search problems. Levels and Voronoi diagrams of order k.

 

8. Range Search.

 

Orthogonal intersection search. Nonintersecting segments in the plane. Dynamic point location. Simplex range search. Half-space range queries. Decomposable search problems. Parametric search.

 

9. Computer Graphics.

 

Hidden surface removal. Binary Space Partitions. Moving viewpoint.

 

10. How Crucial Is Randomness?

 

Pseudo-random sources. Derandomization.

 

Appendix: Tail Estimates.

 

Chernoff's technique. Chebychev's technique.

 

Bibliography.
 
Index.

商品描述(中文翻譯)

描述：

適用於初級研究生級別的計算幾何課程。

這本最新且簡潔的計算幾何入門書籍，強調簡單的隨機方法，旨在為初學者提供快速、易於理解的資料。

 

目錄：

I. 基礎知識。

1. 快速排序和搜索。

 

快速排序。快速排序的另一種觀點。隨機二叉樹。跳躍列表。

 

2. 什麼是計算幾何？

 

範圍查詢。排列。梯形分解。凸多面體。沃羅諾圖。隱藏表面去除。數值精度和退化。早期的確定性算法。確定性與隨機化算法。隨機性模型。

 

3. 增量算法。

 

梯形分解。凸多面體。沃羅諾圖。配置空間。尾部估計。

 

4. 動態算法。

 

梯形分解。沃羅諾圖。歷史和配置空間。重建歷史。刪除歷史。動態洗牌。

 

5. 隨機抽樣。

 

有界價值的配置空間。自上而下抽樣。自下而上抽樣。動態抽樣。平均衝突大小。更多動態算法。範圍空間和E網。比較。

 

II. 應用。

6. 超平面排列。

 

增量構建。區域定理。規範三角形。點定位和射線射擊。點定位和範圍查詢。

 

7. 凸多面體。

 

線性規劃。面數。增量構建。預期的結構和衝突變化。動態維護。沃羅諾圖。搜索問題。等級和k階沃羅諾圖。

 

8. 範圍搜索。

 

正交交叉搜索。平面上的非相交線段。動態點定位。簡單範圍搜索。半空間範圍查詢。可分解的搜索問題。參數搜索。

 

9. 電腦圖形學。

 

隱藏表面去除。二進制空間分割。移動視點。

 

10. 隨機性有多重要？

 

偽隨機源。去隨機化。

 

附錄：尾部估計。

 

切諾夫技巧。切比雪夫技巧。

 

參考文獻。

 

索引。

類似商品