CS 6160-001 Spring 2018 Computational Geometry

Tue/Thu: 1045-1205. WEB L114

Course Mechanics

• 80%: 5-6 Assignments (please read the homework policy)
• 20%: Project (read the project guidelines). 

Policies

• School of Computing Academic Policies
• College of Engineering Guidelines

Lectures

• Core Geometric Objects
• (1/11-1/8) Convex Hulls I: Convexity, representation of convex hulls, the gift-wrapping algorithm, divide-and-conquer, Chan's optimal algorithm, linear classification.  Notes. 
  • Assignment 1 due Jan 29. 
• (1/18-1/25):  Voronoi Diagrams. Notes.
• (1/30-2/6): Delaunay Triangulations (Mount, starting at page 74)
• (2/6-2/20): Arrangements, duality and sweep-line algorithms.
• Data Structures
• (2/27) Range trees & kd-trees (Mount, starting at page 48)
• (3/1) Quad trees (Har-Peled, Chapter 2)
• (3/6) Well-separated pair decompositions (Har-Peled, Chapter 3)
• Sampling and Learning (Har-Peled, Chapter 5)
• VC dimension
• epsilon-nets and epsilon-samples
• discrepancy-based constructions
• High Dimensional Geometry
• SVDs, PCA and MDS
• Random projections (and an application to clustering)
• Near neighbors (see these nice Euclidean LSH notes, and this for the main LSH resource page)
• Core sets and extents (see Chapter 23 from this book)
• The Geometry of Learning
• Kernels and Hilbert spaces
• Support Vector Machines
• The graph Laplacian
• Bregman Divergences. 
• Polyhedra and Optimization
  • Polyhedra
  • Linear programming (2D linear programming)
  • Simplex and Ellipsoid methods