Fall 2011
CSc 437/537 Geometric Algorithms

---

Review: we will meet this Tuesday at 7pm in Gould Simpson, Room 701

General Course Information

• Class Sessions
• MoWed, from 5:00 PM to 6:15 PM. Gould-Simson 906
• Instructor:
• Alon Efrat
• Office Hours: Tuesdays and Thursdays, from 1:00 PM to 2:00 PM, or by appointment

• Prerequisites:
• CSc345 or CSc346 required;
• CSc 445 recommended.

 

• Text:
  
• Required: Computational Geometry Algorithms and Applications, 2nd/3rd ed., by de Berg, van Kreveld, Overmars, and Schwarzkopf (Springer-Verlag, 2000).
  
• Can Help: Computational Geometry in C , 2nd ed., O'Rourke, Joseph. (University Press, 1998.)
  
  

Course Description

The course surveys a list of geometric algorithms and geometric data structure. These algorithms are useful for solving problems in areas such as Visualization, Geographic Information Systems (GIS), VLSI, Robotics, Computer Graphics, Computer Vision, and many other areas. Many of these algorithms are elegant and clever, and have ethtetical value on their own. We would tailor the material of the course to the interests of the participants. Some of the question that would be addressed in the course are

• How to efficiently compute the shortest path of a robot in a room full of obstacles.
• 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 way to compare shapes, for pattern recognition purposes.
• Robustness issues - how to avoid numerical errors that mislead the algorithm. 

Final grade calculation:

·              Final_Grade= 65% * (Hw_Grade)+ 10% *Final_Grade + 10% *MidTerm_Grade + 10%* max( MidTerm_Grade, Final_Grade) + 5% Class_Participations_Grade

·           Homeworks :  About 6 homeworks. All but the lowest are counted, all with the same weight.

 
Tentative Schedule

• Week 1: Introduction, geometric primitives [Chap. 1]
• Week 2: Arrangements of lines and segments [Chaps 2,8]
• Week 3: Triangulate and visibility [Chaps. 3,15]
• Week 4: Linear programming [Chap. 4]
• Week 5: Orthogonal range searching [Chaps. 5,10]
• Week 6: Point location and Binary Space Partitions [Chaps. 6,12]
• Week 7: Voronoi diagrams and Delaunay triangulation [Chaps. 7,9]
• Week 8: Convex hulls [Chap. 11]
• Week 9: Non-orthogonal range searching [Chap. 16]
• Rest of the course - would be tailored to the participants interests.