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
provides an abundance of exercises ranging from
the routine to the very difficult.
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.
trapezoidal decompositions. Voronoi diagrams. History and
configuration spaces. Rebuilding history. Deletions in history. Dynamic
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.
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
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