
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.Topics:
The exact 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 Point location Range searching LPtype problems Intersection Lower bounds Techniques/Paradigms: Sweep Divide and conquer Prune and search Random sampling Dynamization Kinetic data structures Perturbation Applications: Mesh generation Simplification Reconstruction Motion planning Collision detection Hidden surface removal Clustering Administrivia
 Course announcement: PostScript or PDF
 UI Direct call number: 01698
 Credit: 1 unit
 Prerequisite: CS 373 or equivalent, or my permission.
Mathematically and/or algorithmically mature undergraduates are welcome!! Recommended Textbooks:
 Computational Geometry: Algorithms and Applications by Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf (SpringerVerlag, 2nd edition, 2000). Available February 1.
 Computational Geometry in C by Joseph O'Rourke (Cambridge University Press, 2nd edition, 1998).
 I'll also distribute recent conference and journal papers in class and/or on the course web site.
Some useful web pages:
 My Computational Geometry Pages
 Nina Amenta's Directory of Computational Geometry Software
 David Eppstein's Geometry in Action and Geometry Junkyard
 Search the Geometry Literature Database, thanks to René van Oostrum
I talk in pictures not in words. I have no arguments to offer, my figures are my proofs.
Laugh away these truths and facts if you can. Theodore Heisel
The Circle Squared Beyond Refutation (1934)Automatic polygon meter
Analog toy computer item
Triangulate me, moot copy
Goatee community portal
Oatmeal recomputing toy
Optional gutter may come
Typical rommmate tongue
Get your calm emotion, Pat.
Get your campmate lotion
Immature galoot potency
A triplet comet among you
Cut lame emotion  go party!
Operate coital Tommygun
Copulate my rotation gem.
Young male potato metric
Go try tapioca emolument
Ugly poetic monotremata
Magical poem torn out yet
Automatic mangle poetry