Skip to content

Computational Geometry midterm pack - complete markdown version

This pack is meant to stand on its own. The markdown files now include slide digestion, embedded figure crops from the main PDF, professor emphasis pulled from recordings when the transcript made one clear, and homework-style exam prompts placed in the relevant topic files.

Scope

  • Main source: comp_geometry_slides_new.pdf
  • Included pages: 9-321 only
  • Supporting sources folded in: lecture recording transcripts and the assigned homeworks

How to study

  • Read files in numeric order.
  • In each file, do not just skim the summary. Study the slide-by-slide notes, then the What you must be able to say/do in an exam section, then the exam drills at the end.
  • For algorithm files, memorize: problem statement, data structure, algorithm steps, invariant/correctness idea, and time/space bounds.
  • For proof/lower-bound files, memorize the exact direction of the reduction or counting argument. Humans love reversing reductions and then acting surprised on exam day.

Reading order

  1. Coordinate systems and basic geometric entities - pp. 9-18
  2. Polygonal geometry, convexity, planarity, and polyhedra - pp. 19-28
  3. Computational models and complexity language - pp. 29-37
  4. Segment trees as a warm-up search structure - pp. 38-44
  5. Planar straight-line graphs and face-edge structure - pp. 45-46
  6. DCEL representation and auxiliary structures - pp. 47-51
  7. Vector algebra and trigonometric groundwork - pp. 52-57
  8. Orientation tests and signed-area interpretation - pp. 58-62
  9. Primitive formulas and summary - pp. 63-65
  10. Search problem taxonomy and inclusion basics - pp. 66-69
  11. Convex polygon inclusion by left test - pp. 70-71
  12. Simple polygon inclusion by intersection counting - pp. 72-74
  13. Convex polygon inclusion by wedges - pp. 75-77
  14. Star-shaped polygon inclusion by wedges - pp. 78-79
  15. Point location by slab decomposition - pp. 80-85
  16. Plane sweep as a recurring paradigm - pp. 86-90
  17. Chain method: basics, definitions, and query idea - pp. 91-101
  18. Chain method: regular PSLGs and constructing the chain family - pp. 102-109
  19. Chain method: regularization of arbitrary PSLGs - pp. 110-115
  20. Chain method: analysis and wrap-up - pp. 116-117
  21. Triangle refinement: setup and triangulation - pp. 118-122
  22. Triangle refinement: hierarchy, query, storage, and analysis - pp. 123-134
  23. Range searching: problem statement and design space - pp. 135-137
  24. Grid method - pp. 138-141
  25. Quadtree method - pp. 142-151
  26. k-d tree method - pp. 152-160
  27. Direct access methods - pp. 161-173
  28. Range trees - pp. 174-179
  29. Range searching summary - pp. 180-180
  30. Convex hull motivation and why the topic matters - pp. 181-182
  31. Convex hull intuition and preliminaries - pp. 183-185
  32. Convex combinations and dimension-sensitive definitions - pp. 186-189
  33. Equivalent formulations and problem statement - pp. 190-195
  34. Lower bound for convex hull via reduction from sorting - pp. 196-201
  35. Extreme points algorithm - pp. 202-205
  36. Graham’s scan: concept and preparation - pp. 206-214
  37. Graham’s scan: analysis, upper-lower hull view, and summary - pp. 215-219
  38. Jarvis march (gift wrapping) in 2D - pp. 220-224
  39. Quickhull - pp. 225-234
  40. Divide-and-conquer convex hulls and hull union - pp. 235-241
  41. Supporting lines from hull union - pp. 242-244
  42. Dynamic/on-line convex hull insertion: problem setting and core idea - pp. 245-253
  43. Dynamic/on-line convex hull insertion: data structure, search, update, and analysis - pp. 254-263
  44. Gift wrapping in higher dimensions: background and setup - pp. 264-271
  45. Gift wrapping in higher dimensions: algorithm and adjacent facets - pp. 272-279
  46. Gift wrapping in higher dimensions: supporting hyperplanes, initialization, candidates, and analysis - pp. 280-289
  47. Proximity problem family: survey and relations - pp. 290-299
  48. Proximity lower bounds and transformations - pp. 300-307
  49. Closest pair: problem setup and 1D version - pp. 308-313
  50. Closest pair: 2D merge step - pp. 314-319
  51. Closest pair: analysis and higher dimensions - pp. 320-321

Folder map

  • convex-hulls/
  • geometric-objects-notation-and-asymptotic-preliminaries/
  • geometric-search/
  • proximity/
  • pslgs-dcels-vectors-and-geometric-primitives/
  • images/ for figure crops used inside the notes