mshah.ioCourse ScheduleCourse Information
Introduction to (Applied) Computational GeometryTriangles and Polygon TriangulationConvex HullsVoronoi Diagrams and other arrangements and Blender3D ProgrammingGeometric Primitives and CollisionExam during class timeMotion, Planning, and CurvesMesh Representation, Data Structures, and Marching Cubes Mesh Simplification and Topology AlgorithmsMini-lecture Special Topics and Course Wrap-up
Register New Account


CPSC S4794 Applied Computational Geometry Programming

'Math is fun...when you understand the application' -- Your Instructor

The full Course Youtube Playlist

Art Gallery/Triangulations
Data Structures
Geometry Processing
Quick Links | Official class forumPiazza Course Forum |

Schedule/Road Map

The following is our tentative syllabus for the course, changes should be expected throughout the semester. I will announce in class, piazza, or through e-mail any major changes.

Week

Date

Lecture and Readings

Problem Sets

Note(s)

1

Tuesday, 2026-Jun-30
Module 1
Introduction to (Applied) Computational Geometry
  1. Course Structure/Administrivia
  2. Introduction to Computational Geometry
  3. DLang Introduction
  4. SDL Introduction -- creating a window, handling keyboard input
PSET 01 Released (Due July. 7 Anywhere on Earth; Late Deadline July. 9 for up to 90%)
Welcome back to class!

Note: Summer moves fast -- start your PSETS immediately!

1

Thursday, 2026-Jul-02
Module 2
Triangles and Polygon Triangulation
  1. Triangles
  2. Linear Algebra Review and Cross Products
  3. Polygons
  4. Art Gallery Problem
  5. Diagonal's and Coloring Proofs
  6. Polygon Triangulation
  7. Ear Clipping
  8. A few implementation notes
-- --
-- --

2

Tuesday, 2026-Jul-07
Module 3
Convex Hulls
  1. Polygon Partitioning
  2. Plane Sweep
  3. Convex Hulls in 2D
  4. Gift Wrapping
  5. Quick Hull
  6. Closest point to line segment
PSET 02 Released (Due July. 14 Anywhere on Earth; Late Deadline July. 17 for up to 90%)
-- --

2

Thursday, 2026-Jul-09
Module 4
Voronoi Diagrams and other arrangements and Blender3D Programming
  1. Voronoi Diagrams
  2. Delaunay Triangulation
  3. Closest Point
  4. Fortune's Algorithm
  5. 3D Modeling Tools
  6. Programming in Blender3D
-- --
-- --

3

Tuesday, 2026-Jul-14
Module 5
Geometric Primitives and Collision
  1. Collision Detection Strategies
  2. Basic Primitive Tests
  3. minkowski sum/difference
  4. Equation of a line
  5. Segment intersection
  6. SAT - Separating Axis Theorem
PSET 03 Released (Due July. 21 Anywhere on Earth)

(Late Deadline July. 24 for up to 90%)
Final Project Specification released.

Mike in different time zone this week, may be slower to respond to e-mails.

3

Thursday, 2026-Jul-16
Module 6
Exam during class time
  1. Exam
-- --
Exam will open automatically and be taken on canvas during the normal class time.

4

Tuesday, 2026-Jul-21
Module 7
Motion, Planning, and Curves
  1. Introduction to Motion Planning
  2. Graph and Tree Review
  3. Graph Search
  4. A*
  5. Curves (Splines)
PSET 04 Released (Due July. 28 Anywhere on Earth)

(Late Deadline July. 31 for up to 90%)
Previous Year Final Projects

4

Thursday, 2026-Jul-23
Module 8
Mesh Representation, Data Structures, and Marching Cubes
  1. Mesh Representation
  2. Data Structures
  3. Marching Cubes
-- --
-- --

5

Tuesday, 2026-Jul-28
Module 9
Mesh Simplification and Topology Algorithms
  1. Levels of Detail
  2. Mesh Simplification
  3. Mesh Topology
-- --
-- --

5

Thursday, 2026-Jul-30
Module 10
Mini-lecture Special Topics and Course Wrap-up
  1. Mini-Topics: Surface Parameterizeation
  2. Mini-Topics: Shape Analysis
  3. Mini-Topics: BSP Trees
  4. Course Wrap-up! (Last class)
  5. Class Photo (if in person)
'Final project due July 31 (anywhere on Earth, so Aug. 1 around 8am EST). (Note: No extensions for final project; 10% late penalty every day project is late)
Last official day of class :( (We'll do an 'online' class photo)
Please do not redistribute or host any materials without e-mailing me first. Thank you for your time!