Instructor: Joshua A. Levine
Office: 754 GouldSimpson
Meets: M/W 2:003:15pm, 906 GouldSimpson
Office Hours: M 3:304:30pm, T 4:305:30pm (GS 754), or by appointment
TA: Alex Koltz, akoltz@email.arizona.edu
TA Office Hours: M 1:002:00pm (GS 938)
TA: Justin Crum, jcrum@math.arizona.edu
TA Office Hours: F 10:00am11:00am (GS 938)
Course Syllabus
D2L (for 437)
D2L (for 537)
Piazza
Course Calendar
All topics on this page are tentative and subject to change!
All required readings are intended to be read before class begins
Week 
Date 
Monday 
Date 
Wednesday 

1 
Jan 07 
 No Class  
Jan 09 
Introduction 
2 
Jan 14 
2D Convex Hulls 
Jan 16 
Line Segment Intersection 
3 
Jan 21 
 MLK Day  
Jan 23 
Overlay of Subdivisions 
4 
Jan 28 
Polygon Triangulation 
Jan 30 
lowD Incremental LP 
5 
Feb 04 
lowD Randomized LP 
Feb 06 
Range Trees 
6 
Feb 11 
Planar Point Location 
Feb 13 
Randomized Point Location 
7 
Feb 18 
Voronoi Diagrams 
Feb 20 
Variations on Voronoi 
8 
Feb 25 
PointLine Duality 
Feb 27 
Midterm Exam 
9 
Mar 04 
 Spring Break  
Mar 06 
 Spring Break  
10 
Mar 11 
Delaunay Triangulations 
Mar 13 
More Delaunay 
11 
Mar 18 
Alpha Hulls 
Mar 20 
Segment Trees 
12 
Mar 25 
3D Convex Hulls 
Mar 27 
Binary Space Partitions 
13 
Apr 01 
Motion Planning 
Apr 03 
Quadtrees 
14 
Apr 08 
Visibility Graphs 
Apr 10 
Grad Presentations 
15 
Apr 15 
Grad Presentations 
Apr 17 
Grad Presentations 
16 
Apr 22 
Grad Presentations 
Apr 24 
Grad Presentations 
17 
Apr 29 
Grad Presentations 
May 01 
Final Exam Review 
Final Exam: Fri., May 3, 13pm, 906 GouldSimpson
Highlighted dates have a homework assignment due immediately before class begins on that day.
Boxed dates correspond to the day before the deadlines for the dropping (without a W) and the withdraw deadlines for this semester.
See Spring 2019 Undergraduate Dates and Deadlines and Spring 2019 Graduate Dates and Deadlines.
Link to Google drive folder with all lecture slides
Lecture 02  2D Convex Hulls ( slides)
Date: January 14, 2019
Required Reading:
Optional Reading:
Lecture 03  Line Segment Intersection ( slides)
Date: January 16, 2019
Required Reading:
Optional Reading:
Lecture 04  Overlay of Subdivisions
Date: January 23, 2019
Required Reading:
Optional Reading:

Homework 1
 Chs. 12
Assigned: Jan 23
Due: Feb 06 01:59:59 PM
Graded: Feb 13
Homework 2
 Chs. 35
Assigned: Feb 06
Due: Feb 20 01:59:59 PM
Graded: Feb 27
Homework 3
 Chs. 67
Assigned: Feb 20
Due: Mar 13 01:59:59 PM
Graded: Mar 30
Homework 4
 Chs. 89
Assigned: Mar 13
Due: Mar 27 01:59:59 PM
Graded: Apr 03
Homework 5
 Chs. 1012
Assigned: Mar 27
Due: Apr 10 01:59:59 PM
Graded: Apr 17
Homework 6
 Chs. 1315
Assigned: Apr 10
Due: Apr 24 01:59:59 PM
Graded: May 01
