# Computational Geometry

## CS 497 JE, Spring 2002

### TuTh 2:00-3:15, 231 Natural HistoryInstructor: Jeff Ericksonhttp://www.cs.uiuc.edu/~jeffe/teaching/497/

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!

 Objects: 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

• UI Direct call number: 01689
• Credit: 1 unit
• Prerequisite: CS 373 or equivalent, or my permission. Mathematically and/or algorithmically mature undergraduates are welcome!!
• Textbook: Computational Geometry: Algorithms and Applications by Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf (Springer-Verlag, 2nd edition, 2000). I'll also distribute recent conference and journal papers on the course web site.
• Coursework: Grades will be based on homeworks, scribe notes, and a semester project. There will be no exams.