Computational Geometry

CS 497 JE, Spring 2002

TuTh 2:00-3:15, 231 Natural History
Instructor: Jeff Erickson

Computational geometry is the field of theoretical computer science devoted to the design, analysis, and implementation of algorithms and data structures to solve geometric problems. These problems arise in several different areas, including computer graphics, robotics, databases, data mining, parallel computing, statistics, and pure math. Their solutions combine traditional algorithmic techniques with beautiful results from combinatorics, geometry, and other mathematical areas. Computational geometry was the breeding ground for several important techniques that later spread to the broader algorithms community - for example, dynamic data structures, randomized algorithms, and external memory computing - and continues to be one of the most active, interesting, and applicable areas of algorithms research today.

The exact course topics will depend on the interests of the participants, but here is a sample of possibilities. Please let me know if there's something specific you want to talk about!

  • Polygons
  • Convex polytopes
  • Triangulations
  • Voronoi diagrams
  • Convex decompositions
  • Arrangements
  • Visibility graphs
  • Problems:
  • Convex hulls
  • Nearest neighbors
  • Intersection
  • Point location
  • Range searching
  • Linear programming
  • Lower bounds
  • Techniques:
  • Linearization
  • Sweep
  • Divide and conquer
  • Prune and search
  • Random sampling
  • Dynamization
  • Perturbation
  • Applications:
  • Mesh generation
  • Simplification
  • Reconstruction
  • Motion planning
  • Collision detection
  • Robust statistics
  • Clustering