Special Topics in Computational Geometry

Instructor: Valentin Polishchuk Email: valentin@compgeom.com. Tel: 19151239. Office: Exactum, A336.
This is a two-week course, offered 12.05.-21.05.2009. The course meets in room C221 on Tue, Wed, Thu, 12-14.
May 21 is a public holiday. The class is resecheduled for May 22.

Project submission guidelines

Email your code or your survey to the instructor. If you made a web applet, please also send the link.
See the instructor in class on Fri May 22 or Wed May 27. If you can't make it to the class, set a separate meeting time.
If you work in a group: There must be one email per person, not one per group. (It's OK to have the same email sent by each student in the group.) Also, each student has to speak to the instructor about the project.
No email -- no grade. No meeting -- no grade.

If you do an implementation project, email a 1-2 page description of the implementation (what is purpose of the code? what algorithms are used? what programming language? what packages? what is coded by you?)
If you work in a group: There must be one email per person, not per group. The description must be written by you personally. While the project is a group work, the description is your own work. Please clearly indicate what was your personal contribution to the implementation (if you contributed to everything, just say "everything").
No email -- no grade. No meeting -- no grade.

Course outline

I. Motion planning in polygonal domains

Visibility graph approach.
Continuous Dijkstra. Shortest path tree and shortest path map.
Multiple non-crossing paths.

II. Shape modeling

Convex hull, Voronoi diagram, Delaunay triangulation, and their generalizations.
Coresets.

Slides
Applets used in class: k-hull and alpha-shape, alpha-hull, alpha-shape, VD, DT, DT, RNG, GG, MST, beta-skeleton
The first applet is by (our own!) Arto Vihavainen, the others are by students of Godfried Toussaint
Rotating calipers animation, rotating calipers page - applet ~~not working~~ fixed by (our own!) Juan Fernandez Blazquez

Assignments

Each student is expected to participate either in an implementation project, or in writing a survey on one of the following topics: 1) Voronoi diagrams: abstract, furhtest-site, geodesic; 2) Algorithms on unit-disk graphs; 3) Multicommodity flows; 4) Minimum-link paths: bit complexity; 5) Snap rounding; 6) Recongnizing polygon visibility graphs; 7) Minimum-link rectilinear path amidst rectilinear obstacles; 8) Dubins' paths. Some additional implementation projects mentioned in class are: The continuous Dijkstra algorithm for rectilinear shortest path; Shape mining in the sky; Rotating calipers.