An uninflatable polyhedron
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!
Objects: 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
- UI Direct call number: 43808
- Credit: 4 hours
- Prerequisite: CS 473G or equivalent, or my permission. Basic courses in probability, linear algebra, and graph theory are also strongly recommended. Mathematically/algorithmically mature undergraduates are welcome!!
- Recommended textbook: Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer-Verlag, 2nd edition, 2000. Available from Amazon and elsewhere. The first edition is fine. Lecture notes and research papers will also be distributed on the course web site.
- Coursework: Grades will be based on sporadic homeworks, scribe notes, and a semester project. There will be no exams.