Prev Next

Reference materials

Computational Geometry - Methods and Applications (Jianer Chen)

  1. Introduction
  2. Algorithmic Foundations
    1. A computational model
    2. Complexity of algorithms and problems
    3. A data structure supporting Set operations
    4. Geometric graphs in the plane
  3. Geometric Preliminaries
    1. Basic definitions
    2. Convex hulls
    3. Proximity problems
    4. Intersections
    5. Geometric searching
  4. Geometric Sweeping
    1. Intersection of line segments
    2. Constructing convex hulls
    3. The farthest pair problem
    4. Triangulations
  5. Divide and Conquer
    1. Convex hulls again
    2. Voronoi diagram
    3. Constructing a Voronoi diagram
  6. Prune and Search
    1. Kirkpatrick-Scidal's algorithm for convex hulls
    2. Point location problems
  7. Reductions
    1. Convex hull and sorting
    2. Closest pair and all nearest neighbor
    3. Triangulation
    4. Euclidean minimum spanning tree
    5. Maximum empty circle
    6. All farthest vertex
  8. Lower Bournd Techniques
    1. Preliminaries
    2. Algebraic decision trees
    3. Proving lower bounds directly
    4. Deriving lower bounds by reductions
    5. A remark on our model
  9. Geometric Transformations
    1. Mathematical background
    2. Half plane intersections
    3. The smallest area triangle
    4. Convex polygon intersections
  10. Geometric Problems in Higher Dimensions
  11. Dynamization Techniques
    1. Online construction of convex hulls
  12. Randomized Methods
  13. Parallel Constructions