Course Description:
This course covers fundamental and advanced principles for designing and analyzing geometric algorithms and data structures, and their application to other disciplines. Computational Geometry is a young discipline which enjoys close relations to mathematics and to various application areas such as geometric databases, molecular biology, sensor networks, visualization, geographic information systems, VLSI, robotics, computer graphics and geometric modeling. Many geometric algorithms are elegant and clever, and have esthetical value on their own.
This course will cover techniques for designing efficient data structures and algorithms for geometric problems, such as convex hulls, geometric intersections, Voronoi diagrams and Delaunay triangulations, and range searching. Advanced topics may include dynamic and kinetic data structures, shape analysis and matching, robustness and implementation issues, and geometric approximation algorithms.
There will be regular written homework assignments. Undergraduate students will be graded on a different scale and on fewer problems.
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.
Prerequisites:
CMPS 6610/4610 Algorithms or CMPS 3130/6130 Introduction to Computational Geometry or consent of the instructor.
Please do not hesitate to contact the instructor at cwenk -at- tulane -dot- edu
if you have questions.
Class Webpage:
http://www.cs.tulane.edu/~carola/teaching/cmps6640/spring16/
Time & Place:
Tuesdays, Thursdays 11am - 12:15pm, ST 302
Textbooks:
Required:
Lecture notes by David Mount, available
here
Optional References:
- Algorithmic Geometry, Jean-Daniel Boissonnat and Mariette Yvinec, Cambridge University Press, UK, 1998, ISBN-13: 9780521565295
- Computational Geometry: Algorithms and Applications, (3rd
Edition), M.
deBerg, O. Cheong, M. vanKreveld, M. Overmars, Springer-Verlag, 2008, IABN 9783540779735