An uninflatable polyhedron

Computational Geometry

CS 598 JE, Spring 2008

WF 12:30-1:45, 1302 Siebel Center
Instructor: Jeff Erickson

Computational geometry is the field of theoretical computer science devoted to designing, analyzing, and implementing algorithms and data structures to solve geometric problems. These problems arise in many different research areas, including computer graphics, robotics, scientific computing, mobile and sensor networks, spatial and temporal databases, data mining, parallel computing, and robust statistics. Their solutions combine traditional algorithmic techniques with beautiful results from combinatorics, geometry, topology, and other areas of mathematics. Computational geometry was the breeding ground for several important techniques that later spread to the broader theoretical computer science community—for example, dynamic data structures, randomized algorithms, and external-memory algorithms—and it continues to be one of the most active, interesting, and applicable areas of algorithms research today.

Exact course topics will depend on student interest, 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
  • Minkowski sums
  • Visibility graphs
  • Problems:
  • Convex hulls
  • Nearest neighbors
  • Intersection
  • Point location
  • Range searching
  • Linear programming
  • Shape fitting
  • Lower bounds
  • Techniques:
  • Projective duality
  • Plane sweep
  • Divide and conquer
  • Random sampling
  • Linearization
  • Dynamization
  • Perturbation
  • Coresets
  • Applications:
  • Mesh generation
  • Spatial databases
  • Motion planning
  • Surface reconstruction
  • Optimization
  • Robust statistics
  • Dimensionality reduction
  • Computational topology