CSN-523: Computational Geometry
(Spring 2017-2018)

M. Tech. (CSE) I Year, B. Tech. (CSE) IV Year and PhD (CSE)

Course Instructor: Sudip Roy

Teaching Assistants: Ankur Gupta (PhD Student), Sumit Sharma (PhD Student), Debasis Gountia (PhD Student), Rahul Kumar (PhD Student), Anirban Mitra (MTech II Year Student), Arjun Sharma (MTech II Year Student)

 

Course Outline

• This is a course of Four (4) credit.
• It consists of Three (3) lecture hours per week and One (1) hour tutorial.
  
• The basic thrust of the course would be to familiarize the students with the design and analysis of efficient algorithms for geometric problems, typically in low dimensions (2,3,..). Its goal is to make students familiar with the important techniques and results in computational geometry, and to enable them to attack theoretical and practical problems in various application domains. These problems arise in a wide range of areas, including CAD, VLSI, robotics, computer graphics, molecular biology, GIS, spatial databases and sensor networks.
• We will try to stick to the basic course outline as given in Syllabus, but may deviate a bit.
  
• Prerequisite: CSN-212 (Design and Analysis of Algorithms).
• Performance Evaluation: Class Work Sessional (CWS) = 25%, Mid-Term Exam (MTE) = 25%, End-Term Exam (ETE) = 50%.
• CWS (25% marks) will be computed by a weighted sum of different components.

 

General Information

• This is an elective course for M.Tech. (CSE) I year, BTech (CSE) IV year and PhD students (Total Strength: ~70).

• Lecture Class Timings:
  Mondays: 10 - 11 AM, Wednesdays: 10 - 11 AM and Thursdays: 11 AM - 12 NOON
  Lecture Venue: LHC-102, Dept. of CSE

• Tutorial Class Timings:
  Tuesdays (2 - 4 PM), Venue: S-301, Dept. of CSE
  

• Course Webpage: http://faculty.iitr.ac.in/~sudiproy.fcs/courses/csn523_2018.html

• Piazza Course Site: https://piazza.com/iitr.ac.in/spring2018/csn523

• Moodle site: https://moodle.iitr.ac.in/course/view.php?id=33

• Office time to meet the Course Instructor (For any kind of doubt clearing): Monday - Friday (6 - 7 PM)
  (To confirm the availability, please send an email before coming)

 

Study Materials

Books: [Let's see the Cover Pages]
[B1] (JOR) Joseph O'Rourke, Computational Geometry in C, Cambridge University Press.
[B2] (Four Authors) M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf, Computational Geometry: Algorithms and Applications (2nd Edition), Springer-Verlag.
[B3] Franco P. Preparata and Michael Ian Shamos, Computational Geometry: An Introduction, Springer-Verlag.
[B4] Joseph O'Rourke, Art Gallery Theorems and Algorithms, Oxford University Press, 1987 (Available Online).
[B5] Subir Kumar Ghosh, Visibility Algorithms in the Plane, Cambridge University Press.

References:
[R1] Lecture notes by Prof. David Mount, Department of Computer Science, University of Maryland, USA.
[R2] Website of Joseph O'Rourke: Homepage, Papers
[R3] CGAL: Computational Geometry Algorithms Library

---------------------------------------------------------------------------------