| Date
| Topics
| Lecture sections
| Handouts
| Announcement
|
| August 25
| Introduction
| Chapters 1-3
| Chapters 1-3
|
|
| August 27
| Preliminaries in geometry
| Sections 2.1-2.3
|
|
|
| August 29
| Data structures in geometric computation
| Section 2.4
|
|
|
| September 1
| Labor day
|
|
|
|
| September 3
| Intersections of line segments
| Section 4.1
| Chapter 4
|
|
| September 5
| Convex hull: preliminaries
| Section 3.1
|
|
|
| September 8
| Convex hull: Jarvis March
| Section 4.2.1
|
|
|
| September 10
| Convex hull: Graham Scan
| Section 4.2.2
|
|
|
| September 12
| The farthest-Pair problem
| Section 4.3
|
|
|
| September 15
| Triangulating a monoton polygon
| Section 4.4.1
|
|
|
| September 17
| Monoton polygon triangulation: correctness
| Section 4.4.1
|
|
|
| September 19
| Regularization of a general PSLG
| Section 4.4.2
|
| Homework 1 posted
|
| September 22
| Data structures for PSLG regularization
| Section 4.4.3
|
|
|
| September 24
| PSLG Triangulating: summary
| Section 4.4
|
|
|
| September 26
| Divide-and-Conquer techniques
| Chapter 5
|
|
|
| September 29
| MergeHull and QuickHull
| Section 5.1
| Chapter 5
|
|
| October 1
| Voronoi diagram: definition and properties
| Section 5.2
| Animation
|
|
| October 3
| Voronoi diagram: divide-and-conquer
| Section 5.3
|
|
|
| October 6
| Voronoi diagram: sigma-chain
| Section 5.3
|
|
|
| October 8
| Voronoi diagram: merge in liear time
| Section 5.3
|
|
|
| October 10
| Voronoi diagram: further discussions
| Section 5.3
|
|
|
| October 13
| Fall break
|
|
|
|
| October 15
| Prune and search: general framework
| Chapter 6
| Chapter 6
| Homework 2 posted
|
| October 17
| Kirkpatrick-Seidel algorithm
| Section 6.1.1
|
|
|
| October 20
| Chan's algorithm
| Section 6.1.2
| Chapter 6
| Chapter 6 updated
|
| October 22
| Point location: on convex polygons
| Section 6.2.1
|
|
|
| October 24
| Point location: slab method
| Section 6.2.2
|
|
|
| October 27
| Point location: Kirkpatrick's algorithm
| Section 6.2.4
|
|
|
| October 29
| Linear-time reduction
| Sections 7.1-7.2
| Chapter 7
|
|
| October 31
| Delaunay triangulation
| Section 7.3
| Delaunay triangulation
| Chapter 7 posted
|
| November 3
| Euclidean minimum spanning tree
| Section 7.4
|
|
|
| November 5
| Maximum empty circle
| Sections 7.5
|
| Homework 3 posted
|
| November 7
| Introduction to computational lower bounds
| Section 8.1
|
|
|
| November 10
| Linear decision tree model
| Section 8.2
|
|
|
| November 12
| Algebraic decision tree model
| Section 8.2
|
|
|
| November 14
| Ben-or's Theorem
| Section 8.2
| Chapter 8
| Chapter 8 posted
|
| November 17
| Lower bounds: Closest Pairs and others
| Section 8.3.1
|
|
|
| November 19
| Lower bounds: Convex Hull and others
| Section 8.3.4
|
|
|
| November 21
| Lower bounds: Farthest-Pairs and others
| Sections 8.3.2 and 8.3.4
|
|
|
| November 24
| Euclidean Travelling Saleman Problem
| Lecture notes ETSP
| ETSP
| Lecture Notes on ETSP posted
|