Computer Science

My Instructor Resource Center : Log in or request access

Computational Geometry: An Introduction Through Randomized Algorithms
Ketan Mulmuley, The University of Chicago

ISBN-10: 0133363635
ISBN-13: 9780133363630

Publisher: Prentice Hall
Copyright: 1993
Format: Paper; 447 pp
Published: 06/08/1993
Status: Available on Demand What's this?

Suggested retail price: $65.00
Buy from myPearsonStore

Request a printed exam copy

Email this page to a colleague
Prepare for the First Day of Class
Learn about customization options

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.

first develops basic principles with the help of very simple planar applications — beginning with deterministic algorithms and shifting to randomized algorithms as the problems become more complex.

then explores higher dimensional advanced applications in the second part.

provides an abundance of exercises — ranging from the routine to the very difficult.

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.

Algorithms (Computer Science)

Discipline & Course Resources

Interwrite Personal Response System
EduCue, Addison-Wesley & Benjamin Cummings
©2004 | Prentice Hall | Electronic Supplement | Instock
ISBN-10: 0321267354 | ISBN-13: 9780321267351

Pearson Higher Education offers special pricing when you choose to package your text with other student resources. If you're interested in creating a cost-saving package for your students contact your Pearson Higher Education representative.