• Course Outline

  In many areas of computer science it is necessary to store, analyze, and create or manipulate spatial data. Examples are robotics, computer graphics and virtual reality, and geographic information systems. This course deals with the algorithmic aspects of these tasks: we study the design and analysis of geometric algorithms and data structures.



• Class Meetings
  • yet to be decided
  • yet to be decided
  • yet to be decided


• Web Resources:
  
  CSL852, Computational Geometry, Sen, S., IIT Delhi
  
  Computational Geometry Lecture Notes by David M. Mount
  
  Computational Geometry Lecture Notes by Bernd Gärtnerand Michael Hoffmann


• The necessary evil - marks, exam, etc.

  The evaluation for the course will be based on midterm, assignments and final exam.There will be 4-6 assignments that will carry weightage for your final evaluation and in particular, solving them will be useful for getting good marks in the exams.



• Some cautionary notes

  This course is essentially a problem solving course, and so there will be lots of problems in the form of practice problems. Anything you hand in is assumed to be done by you on your own. If you had consulted any resource (including books, internet, or other persons), then please mention that in the work you hand in. Copying from any source without acknowledgement will result in unwanted consequences for everyone!

Topics that we want to cover: (not limited to and not necessarily in this order)

1. Introduction
2. Convex Hull
3. Line Sweep Method
4. Closest Pair
5. Planar Subdivision
6. Point Location
7. Voronoi Diagram
8. Delaunay Triangulation.
9. Arrangements
10. Triangulation of Arbitrary Polygon.
11. Visibility Problems
12. Range Searching
13. Randomized Incremental Construction 1
14. Randomized Incremental Construction 2
15. Epsilon-Nets & VC Dimension

Assignments

• Berg, M., D., Kreveld, M., V., Overmars, M., and Schwarzkopf, O., Computational Geometry: Algorithms and Applications, 3rd Edition, Springer, 2008


• Preparata, F., and Shamos, M., Computational Geometry: An Introduction, Springer-Verlag, 1985


• Mulmuley, K., Computational Geometry: An Introduction Trough Randomized Algorithms, Prentice-Hall, 1994