AMS 345/ CSE 355 Computational Geometry, Fall 2015

The course meets Tues/Thur, 11:30--12:50 in Light Engineering 102.

Joe's Office Hours (tentative):

Tues (10:00-11:15) and Wed (2:00-3:30), and please drop by any time, or send email or call

Teaching Assistants:

Chen Cai (; Mondays, 10:00-12:00;
Mei Li (; Wednesdays, 4:00-6:00pm (in Harriman 010)


Welcome to AMS 345/CSE 355!
The TAs for the course are
Chen Cai (; office hours Mondays, 9:30-11:30 (updated 9/18/15);
Mei Li (; Wednesdays, office hours 5:00-7:00pm (in Harriman 010)

On-Line Versions of Handouts from Class:

Course Information (AMS 345), Fall 2015 (available soon!)
Assignments, handouts, practice exams, and solutions to assignments will be available via Blackboard.
The introductory class on Tuesday, August 25 will give an overview of what computational geometry is and what types of problems we study in the course. I will include some demos, which are applets linked from the slides (available on Blackboard).

Links of Possible Interest:

  • Interview questions for your next job interview -- enjoy!
  • Art Gallery Problem applet, which allows you to mouse in a polygon and watch as it computes a set of vertex guards, as given by Fisk's proof.
  • MathWorld page about the Art Gallery Theorems
  • Interactive Ear Clipping and Mouth Closing applet, with nice details about the Two-Ears Theorem and the One-Mouth Theorem (of homework set 1)
  • camera avoidance, a cute program to find a "best" path to avoid being seen by cameras
  • Convex hull algorithm applets
  • Voronoi applications page
  • Uniform polyhdera, a cool site found by Randy Sprouse
  • Delaunay/Voronoi applet by Paul Chew
  • shortest path in simple polygon, with horizontal trapezoidization, triangulation, "random" simple (monotone) polygon; by Josh Tyler

    Miscellaneous Links of Relevance:

  • Textbook by Devadoss and O'Rourke, entitled Discrete and Computational Geometry.
  • Textbook by O'Rourke, entitled Computational Geometry in C, 2nd Edition
  • Recommended textbook, by de Berg, Cheong, van Kreveld, and Overmars (3rd ed, 2008).
  • David Mount's course notes on CG
  • Computational Geometry at Stony Brook
  • The Open Problems Project (TOPP), Erik Demaine, Joe Mitchell, and Joe O'Rourke
  • Jeff Erickson's Geometry Page
  • CompGeom Bibliography Page
  • David Eppstein's Geometry in Action
  • David Eppstein's Geometry Junkyard
  • David Eppstein's General Geometric References
  •, page of Chris Gold
  • Strategic Directions in Computational Geometry: Working Group Report - Roberto Tamassia et al
  • Zometool: Ball and stick building toy/tool for geometers
  • CGAL, the Computational Geometry Algorithms Library
  • Directory of Computational Geometry Software