CPS 234: Computational Geometry



CPS 234: Summary of Lectures



Lect. Date Topics Reading
1 Jan. 16 Introduction, Model of computation,
lower bounds
PS: Chapt. 1
2 Jan. 21 Segment trees, interval trees,
priority-search trees
segment intersection
PS: Sect. 1.2.3, 8.8
Meh: Sect. 5.1.2
PS: Sect. 7.2.3
3 Jan. 28 Sweep-line algorithm, map overlay
Planar convex hulls: Graham scan, Jarvis march,
on-line algorithm, optimal algorithms
PS: Sect. 7.2.3
PS: Chapter 3
4 Feb. 4 Convex polytopes, duality
Convex hulls in higher dimensions
Ed Chapt 1
PS: Chapter 3
5 Feb. 11 Convex hulls: Randomized algorithm Mul, Chapter 3
6 Feb. 27 Segment intersection: Randomized algorithm
Diameter, width, normal diagram
Mul, Chapter 4
PS, Chapter 4
7 March 4 Voronoi diagram: definition, properties, relationship with convex hulls
Algorithms: randomized and deterministic
PS, Chapter 5
Mul, Chapter XX
8 March 6 Point location: slab method, persistent data structure
monotone chain method, fractional cascading
PS, Chapter 2
9 March 25 Linear programming: algorithms in fixed dimensions;
Megiddo's 2d algorithm; Seidel's algorithm
PS, Chapter 7
10 April 1 Linear programming: Clarkson's algorithm; LP-type problems
Parametric searching: slope selection
[AS96]
11 April 8 Arrangements of lines and hyperplanes Edels
12 April 10 Orthogonal range searching
Simplex range searching
PS, Chapte 2
[Mat]
13 April 15 Practical data structures: quadtree, kdtrees, bsp's
N-body problem
PS, Chapte 2
14 April 22 Ray tracing, hidden surface removal
15 April 29 Degneracies and robustness issues [Hof89]


Handouts:




Agarwal's Home Page

Return to CPS 234 Homepage.