Spring 2019

Instructor: Joshua A. Levine
Office: 754 Gould-Simpson
Meets: M/W 2:00-3:15pm, 222 Social Sciences
Office Hours: M 3:30-4:30pm, T 4:30-5:30pm (GS 754), or by appointment

TA: Alex Koltz, akoltz@email.arizona.edu
TA Office Hours: M 1:00-2:00pm (GS 938)
TA: Justin Crum, jcrum@math.arizona.edu
TA Office Hours: F 10:00am-11: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 low-D Incremental LP
5 Feb 04 low-D Randomized LP Feb 06 Range Trees
6 Feb 11 Trapezoidal Maps Feb 13 Point Location
7 Feb 18 Voronoi Diagrams Feb 20 Variations on Voronoi
8 Feb 25 Point-Line Duality Feb 27 Midterm Exam
9 Mar 04 -- Spring Break -- Mar 06 -- Spring Break --
10 Mar 11 Line Arrangements Mar 13 Delaunay Triangulations
11 Mar 18 Delaunay, Part 2 Mar 20 Alpha Hulls
12 Mar 25 Segment Trees Mar 27 3D Convex Hulls
13 Apr 01 Binary Space Partitions Apr 03 Motion Planning
14 Apr 08 Quadtrees Apr 10 Visibility Graphs
15 Apr 15 Surface Reconstruction 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, 1-3pm, 222 Social Sciences

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 01 - Introduction

Date: January 09, 2019

Required Reading:

Lecture 02 - 2D Convex Hulls

Date: January 14, 2019

Required Reading: Optional Reading:

Lecture 03 - Line Segment Intersection

Date: January 16, 2019

Required Reading: Optional Reading:

Lecture 04 - Overlay of Subdivisions

Date: January 23, 2019

Required Reading: Optional Reading:

Lecture 05 - Polygon Triangulation

Date: January 28, 2019

Required Reading: Optional Reading:

Lecture 06 - low-D Incremental LP

Date: January 30, 2019

Required Reading: Optional Reading:

Lecture 07 - low-D Randomized LP

Date: February 04, 2019

Required Reading: Optional Reading:

Lecture 08 - Range Trees

Date: February 06, 2019

Required Reading: Optional Reading:

Lecture 09 - Trapezoidal Maps

Date: February 11, 2019

Required Reading: Optional Reading:

Lecture 10 - Point Location

Date: February 13, 2019

Required Reading: Optional Reading:

Lecture 11 - Voronoi Diagrams

Date: February 18, 2019

Required Reading: Optional Reading:

Lecture 12 - Variations on Voronoi

Date: February 20, 2019

Required Reading: Optional Reading:

Lecture 13 - Point-Line Duality

Date: February 25, 2019

Required Reading: Optional Reading:

Lecture 15 - Line Arrangements

Date: March 11, 2019

Required Reading: Optional Reading:

Lecture 16 - Delaunay Triangulations

Date: March 13, 2019

Required Reading: Optional Reading:

Lecture 17 - Delaunay, Part 2

Date: March 18, 2019

Required Reading: Optional Reading:

Lecture 18 - Alpha Hulls

Date: March 20, 2019

Required Reading: Optional Reading:

Lecture 19 - Segment Trees

Date: March 25, 2019

Required Reading: Optional Reading:


Lecture 21 - Binary Space Partitions

Date: April 01, 2019

Required Reading: Optional Reading:

Lecture 22 - Motion Planning

Date: April 03, 2019

Required Reading: Optional Reading:

Lecture 23 - Quadtrees

Date: April 08, 2019

Required Reading:

Lecture 24 - Visibility Graphs

Date: April 10, 2019

Required Reading: Optional Reading:

Lecture 25 - Surface Reconstruction

Date: April 15, 2019

Required Reading: Optional Reading:

Lecture 26 - Grad Presentations

Date: April 17, 2019

Presentations:
  • Brian Bell: Simplicial Depth
  • Kairong Jiang: Range Assignment
  • Brandon Neth: Grey Linear Programming
Optional Reading:

Lecture 27 - Grad Presentations

Date: April 22, 2019

Presentations:
  • Ripan Chowdhury: A thorough overview of Convex Hulls
  • Jackson Lindsay: Kinetic Data Structures
  • Dwight Nwaigwe: A Conjectured Expected Linear Time Convex Hull Algorithm for Points Uniformly Distributed on the Unit Square
Optional Reading:

Lecture 28 - Grad Presentations

Date: April 24, 2019

Presentations:
  • Becca Faust: Bentley-Ottman Line Segment Intersection
  • Craig Thompson: Euclidean Minimum Spanning Trees
  • Xueheng Wan: Visualizing Convex Hull Algorithms
Optional Reading:

Lecture 29 - Grad Presentations

Date: April 29, 2019

Presentations:
  • Carlos Carbajal: Implementing Convex Hulls
  • Spencer Krieger: Sweep Line Algorithms
  • Renee Zhang: Weighted Voronoi Diagrams
Optional Reading:

Final project info
for 537 students

Proposals Due: Feb 22


Homework 1 - Chs. 1-2
  Assigned: Jan 23
  Due: Feb 06 01:59:59 PM
  Graded: Feb 13

Homework 2 - Chs. 3-5
  Assigned: Feb 06
  Due: Feb 20 01:59:59 PM
  Graded: Feb 27

Homework 3 - Chs. 6-7
  Assigned: Feb 20
  Due: Mar 13 01:59:59 PM
  Graded: Mar 30

Homework 4 - Chs. 7-9
  Assigned: Mar 13
  Due: Mar 27 01:59:59 PM
  Graded: Apr 03

Homework 5 - Chs. 9-11
  Assigned: Mar 27
  Due: Apr 10 01:59:59 PM
  Graded: Apr 17

Homework 6 - Chs. 12-15
  Assigned: Apr 10
  Due: Apr 24 01:59:59 PM
  Graded: May 01