• 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]
  • 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; [MR]: 237-239
  • 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 this time
  • A point-line duality transformation      [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   --- AR
  • Two more algorithms for MEB      [dB]: 86-89; [PS]: 297-299
  • Diameter, width      [PS]: 178-182
  • Approximate directional width queries      [Mnote]: 1-5
• More proximity
  • Closest pair of points via rand incr      [KT]: 741-750
  • Stretch factor of Θ-graph      [NS]: 9-12, 63-69
  • Well-separated pair decomposition      [Mnote]: 1-9, 1-6
  • ANN search using quadtree      [Pnote]: 182-184   --- not covered this time
  • 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



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


• Several additional resources are provided where necessary.
• AR stands for additional reading (no lecture delivered but included in syllabus).

---