• Computational Geometry
• CS502 at IITG by R. Inkulu

---

• Overview      [note]
• Orthogonal range queries
  • Bentley-Shamos locus approach      [PS]: 36-39
  • Quadtree      [dB]: 309-313
  • BBST for points on a line      [dB]: 96-99
  • Kd-tree      [dB]: 99-105
  • Range tree      [dB]: 105-109
  • Layered range tree      [dB]: 111-115
  • Priority search tree      [dB]: 226-230
• Stabbing queries
  • Segment tree      [dB]: 232-235
  • Interval tree      [dB]: 221-224
• Doubly-connected edge list      [dB]: 29-33
• Convex hulls
  • Introduction      [dB]: 2-4; [note]: 1-2
  • Jarvis's, Graham's, Chan's      [PS]: 104-112; [Chan '96]: 2-3
  • Quickhull, Shamos's      [PS]: 112-117
  • Preparata-Hong's, Kirkpatrick-Seidel's      [PH'77]: 3-4; [KS'86]: 3-7
  • Incremental, randomized incremental      [dB]: 2-8; [note]
  • Dynamic maintenance      [PS]: 124-131   --- not covered this time
• Intersections
  • Intersections of line segments      [dB]: 20-29
  • Overlay of two subdivisions      [dB]: 33-40
  • Intersection of two convex polygons      [dB]: 67-70   --- AR
  • Binary plane partitions      [dB]: 259-267
• LP in the plane
  • Introduction      [dB]: 66-67, 71-73
  • A rand incr algorithm      [dB]: 73-79
  • Recognizing unbounded LP      [dB]: 79-82
  • A prune and search algorithm      [PS]: 290-297
• Polygon triangulation
  • Existence and naive algorithms      [dB]: 46-47; [twoear]
  • Triangulating a monotone polygon      [dB]: 55-58
  • Triangulating a PSLG      [dB]: 49-55, 58-59
• Art gallery theorem      [dB]: 47-48
• Point location
  • Simple polygon inclusion      [PS]: 41-45
  • The slab method      [PS]: 45-48
  • Compressed quadtree      [Pnote]: 25-26, 15-16
  • Triangulation refinement      [PS]: 56-60
  • Trapezoidal map      [dB]: 124-137
• Arrangement of lines
  • Introduction      [dB]: 179-181, 185-186; [more]
  • Computing via zone theorem      [dB]: 181-185
  • k-Sets and k-levels: combinatorics      [note]   --- not covered
  • A point-line duality transform      [dB]: 177-179, 186
  • A few applications of duality map      [dB]: 179, 186, 253-254; [more]
• Half-plane range queries
  • Partition tree      [dB]: 336-342
  • Cutting tree      [dB]: 346-349; [Mat]: 73-75
• Voronoi diagrams
  • Properties      [dB]: 148-151; [PS]: 206-209, 221-222, 258-259
  • Fortune's sweep line algorithm      [dB]: 151-159
  • A divide and conquer algorithm      [PS]: 213-218
  • A lifting map based algorithm      [dB]: 254-255
• Point set triangulation
  • Introduction      [dB]: 193-194; [note]
  • Intro to Delaunay triangulation      [dB]: 194-199; [PS]: 209-211, 227
  • Lawson's edge-flip algorithm for DT      [dB]: 194-208
  • A lifting map for DT      [SiN]: 7-9
• More extent measures
  • Maxima of a point set      [PS]: 158, 159-160
  • Two applications of FPVD      [dB]: 164-165, 167
  • Two more algorithms for MEB      [dB]: 86-89; [PS]: 297-299
  • Diameter, width      [PS]: 178-182
• More proximity
  • Closest pair of points via rand incr      [KT]: 741-750
  • Well-separated pair decomposition      [Mnote]: 1-9, 1-6
  • Shortest path via visibility graph      [dB]: 325-330
  • Minkowski sums in path planning      [dB]: 284-286, 290-297
• Worst-case lower bounds
  • A few reductions      [PS]: 99, 100, 172, 176-177, 193-194, 212, 260, 289
  • Linear decision trees      [PS]: 30-33, 192, 260



---



• This is an elective course, offered for both undergrad and grad students. It introduces data structures and algorithms to efficiently compute solutions to a number of (discrete) geometric problems. The following are the topics to be covered -
  
  Data structures: range searching, stabbing queries, quadtree, decomposition of points, planar partitions.
  
  Algorithm design techniques: plane sweep, randomized incremental, grids, geometric duality, random sampling, locus approach, vertical decomposition, rotating calipers, preprocess-query, output-sensitive; and, the traditional ones, divide and conquer, greedy, dynamic programming, and prune and search.
  
  Providing worst-case lower bounds on the time complexity of geometric problems via reductions while introducing linear decision trees.
  
  Problems pursued: point location, convex hulls, Voronoi diagrams, triangulations, intersections, extent measures, arrangements, closest pairs, nearest neighbours, visibility, art gallery, shortest paths, linear programming, etc.



• Texts:
• Computational Geometry: Algorithms and Applications by Mark de Berg et al., Third Edition.   [dB]
• Computational Geometry: An Introduction by Franco P. Preparata and Ian Shamos.   [PS]
• [Additional resources are provided where necessary.]


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


• Lectures are held in Slot B: In 5203 on Mon 10-10:55 3-3:55 and Fri 9-9:55, and in 5001 on Th 9-9:55 Wed 3-3:55.
• The academic calendar is here.


• Teaching Assistants: None.


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

  exam1	14 points	8:15-9:45 am on 20th Aug (Sat) in seminar room
  mid-sem	18	2 hours; refer to institute time table
  exam3	15	8:15-9:45 am on 22nd Oct (Fri) in seminar room
  end-sem	25	3 hours; refer to institute time table
  presentation	10	mutual convenience
  class participation	4	-

---