• Computational Geometry
• CS502 at IITG by R. Inkulu

---

• This course is an elective, offered primarily for undergrads. It introduces data structures and algorithms to efficiently compute solutions to a number of (discrete) geometric problems that have innumerable applications. I offered this course last time, in Fall 2022.
  
  The data structures presented help in range searching, answering stabbing queries, storing planar subdivisions, point location, decomposing points, finding nearest neighbours, etc.
  
  Apart from the traditional algorithm design techniques, such as divide and conquer, greedy, dynamic programming, prune and search, and random sampling, the three techniques native to computational geometry, plane sweep, randomized incremental, and grids, are emphasized.
  
  Several relevant introductory theorems from combinatorial geometry on convexity, point-line incidences, point-line duality with an intro to inversive geometry, arrangements, lower envelopes, and the lifting map are presented.
  
  Worst-case lower bounds on the time complexity of geometric problems are established via reductions that introduce linear decision trees.
  
  The problems pursued include computing convex hulls, Voronoi diagrams, triangulations, intersections, extent measures, arrangements, closest pairs, nearest neighbours, visibility, guarding, shortest paths, path planning, spanner networks, linear programming, etc.
  



• Texts: TBA.


• Prereqs: CS101, CS201, CS203, CS205, CS207.


• Lecture schedule: TBA.


• Teaching Assistants: None.


• The grading is relative, and it is based on the total marks obtained in the following:
  
  

  exam1	14 points	10 am to 11:40 am on ? (Sat) in ?
  mid-sem	18	2 hours; refer to institute time table
  exam3	15	10 am to 11:40 am on ? (Sat) in ?
  presentation	10	30 minutes; papers are TBA
  end-sem	25	3 hours; refer to institute time table
  class participation	4	-

---