Home

Course Description:

This course will survey a list of geometric algorithms and geometric data structures. Computational Geometry is a young discipline which enjoys close relations with algorithms and data structures, discrete geometry, topology, graph theory and combinatorics. Techniques from Computational Geometry are applied in areas such as databases, sensor networks, visualization, geographic information systems (GIS), VLSI, robotics, computer graphics, and computer vision. Many geometric algorithms are elegant and clever, and have esthetical value on their own. The material of the course will be tailored to the interests of the participants. Some of the question that will be addressed are:

How to efficiently compute the shortest path of a robot in a room full of obstacles.
How to place security guards (or cameras) in an art gallery.
How to compute the convex hull, the Voronoi diagram and the Delaunay triangulation of a point set.
Given a map of rivers and a map of roads, find all the points where a road crosses a river.
How to simplify a map, or a curve of a function, without loosing too much of the information.
Efficient ways to compare shapes, for pattern recognition purposes.
Robustness issues - how to avoid numerical errors that mislead the algorithm.

There will be regular homework assignments. Homeworks will mostly consist of written problems but may also contain some programming projects. Graduate students will receive a different set of more advanced homework problems and they will be required to read and present a recent research paper on Computational Geometry. The graduate section of this class counts as a CS elective in the CS PhD program.

Please visit the resources page for links to demos and other relevant resources. A good introduction to some computational geometry problems can be found here.

Textbooks:

Computational Geometry: Algorithms and Applications, (3rd Edition), M. deBerg, M. vanKreveld, M. Overmars, O. Schwarzkopf, Springer-Verlag, 2008, IABN 9783540779735
Lecture notes by David Mount

Optional:

Computational Geometry in C (2nd edition), J. O'Rourke, Cambridge University Press, 2001, ISBN 0521649765

Instructor:

Carola Wenk
Stanley Thomas, 303F
E-mail: cwenk -at- tulane -dot- edu
Phone: 504-865-5805
Office hours: M 12pm - 1pm, T 5pm-6pm, and by appointment
For the remainder of the semester office hours will be held on Zoom. The link for the Zoom room for this class is available on Canvas.

Last modified by Carola Wenk, cwenk -at- tulane -dot- edu,

Home

Course Description:

Prerequisites:

Class Webpage:

Time & Place:

Textbooks:

Instructor: