Convex Hulls, Line Segment Intersections, Polygon Triangulation, Linear Programming, Voronoi Diagrams, Delaunay Triangulation, Point Location, Robot Motion Planning, Binary Space Partition, Special Topics.

Semester:

January/June Intersem

Rationale:

To provide students with an introduction to both the theory and applications of the discipline of computational geometry which is concerned with the solving of computational problems arising from geometric questions. Essential theory and algorithms will be covered and content will be motivated by practical problems.Implementations of geometric algorithms in a high-level language will be covered.Course will be seminar-style.

Catalog Description:

Convex Hulls, Line Segment Intersections, Polygon Triangulation, Linear Programming, Voronoi Diagrams, Delaunay Triangulation, Point Location, Robot Motion Planning, Binary Space Partition, Special Topics.

Credits:

3(3-0)

Prerequisite:

Data Structures and Algorithms, or Instructor Consent.

Course Outline:

Convex Hulls

1. Properties
2. Algorithms
3. Handling Degeneracy and Robustness
4. Applications Domains

Line Segment Intersections

1. Algorithms
2. Plane Sweep Method
3. Doubly-Connected Edge List
4. Application Domains

Polygon Triangulation

1. Properties
2. Algorithms
3. Applications Domains

Linear Programming

1. Geometric View of Linear Programming
2. Two-variable Linear Programming: Intersecting Half-Planes
3. Incremental Linear Programming
4. Randomized Linear Programming: Backward Analysis
5. Linear Programming in Higher Dimensions

Voronoi Diagrams

1. Properties
2. Algorithms
3. Application Domains

Delaunay Triangulation

1. Point Set Triangulation
2. Properties: Delaunay Triangulation as Dual of the Voronoi Diagram
3. Algorithms
4. Application Domains

Point Location

1. Trapezoidal Maps
2. Randomized Incremental Algorithms

Robot Motion Planning

1. Work space and Configuration Space
2. Point Robots
3. Motion Planning Techniques

Binary Space Partition

1. Properties
2. Painter's Algorithm
3. Construction

Special Topics

Textbook:

M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf:

Computational Geometry: Algorithms and Applications (2nd Edition), Springer-Verlag, 2000.

Reference Books:

J-D. Boissonnat and M. Yvinec:

Algorithmic Geometry, Cambridge University Press, 1998.

K. Mulmuley:

Computational Geoemetry: An Introduction through Randomized Algorithms, Prentice Hall, 1998.

J. O'Rourke:

Computational Geometry in C (2nd Edition), Cambridge University Press, 1998.

F. P. Preparata and M. I. Shamos:

Computational Geometry: An Introduction, Springer-Verlag, 1991.

Journals and Magazines:

International Journal of Computational Geometry and Applications, World Scientific.

Computational Geometry: Theory and Applications, Elsevier.

Grading System:

The final grade will be computed from the following constituent parts: assignments (30-40%), programming projects (30-40%) and presentations (30-40%).Open/closed-book examination is used for both mid-semester and final exam.

Instructor:

Dr. Sumanta Guha

Contact us: Olivier Nicole

Last update: May 2008