CS268 Class Schedule, Fall Quarter '16-'17
| Below are the key dates for the class (subject to revision). |
|
Monday |
Wednesday |
|
September 26 |
September 28 |
|
Class Introduction and Mechanics; Geomeric Duality; Line Arrangements in the Plane Reading: Basic Algorithms ... notes |
Combinatorics of Arrangements; Zone Theorem; Incremental Arrangement Computation Reading: Basic Algorithms ... notes |
|
October 03 |
October 05 |
|
Straight and Topological Line Sweeps Reading: Basic Algorithms ... notes |
Davenport-Schinzel Sequences and Lower Envelopes; Arrangements in Higher Dimensions Reading: Basic Algorithms ... notes, Lower Envelopes notes |
|
October 10 |
October 12 |
|
Voronoi and Delaunay Diagrams and their Properties Reading: Basic Algorithms ... notes Homework 1 out |
The CCW and InCircle Geometric Primitives; Alpha Shapes Reading: Basic Algorithms ... notes, Ruler, Compass and Computer report |
|
October 17 |
October 19 |
Divide & Conquer Delaunay Algorithm Reading: Basic Algorithms ... notes, |
Randomized Incremental Delaunay Algorithm Reading: Basic Algorithms ... notes |
|
October 24 |
October 26 |
|
Point Location in Planar Subdivisions; The Monotone Chains Method Reading: Point Location ... notes, Optimal Point ... paper Homework 1 due; Homework 2 out |
Hierarchical Point Location; Simple Polygons and their Properties; Shortest Paths Reading:Optimal Search ... paper, Simple Polygon notes, Shortest Path notes |
|
October 31 |
November 02 |
Randomized Incremental Vertical Decompositions; Seidel's Simple Polygon Triangulation Algorithm Reading: Mount lecture notes, Lectures 9 and 10 (pp. 45-53); Seidel algorithm notes |
Randomized Incremental Linear Programming; Minimum Spanning Circles Reading: de Berg et al book, Chapter 4 |
|
November 07 |
November 09 |
|
Geometric Divide and Conquer; Cuttings; Randomized and Deterministic Algorithms Homework 2 due; Homework 3 out |
Ham-Sandwich Theorems; Decimation Reading: Megiddo paper, Kirkpatrick-Seidel paper
|
|
November 14 |
November 16 |
Approximation algorithms and core sets Reading: DukeNotes |
In-class Midterm
|
|
November 21 |
November 23 |
|
No class: Thanksgiving Holiday |
No class: Thanksgiving Holiday |
|
November 28 |
November 30 |
Geometric Range Searching I; Partition Trees Reading: RSnotes1, Matousek paper |
Geometric Range Searching II; Simplicial Partitions |
|
December 05 |
December 07 |
Introduction to Computational Topology I Reading: Slides I, Topology and Data Homework 3 due |
Introduction to Computational Topology II Reading: Slides II, Barcodes, Persistent Homology
|