CSC 274: Discrete & Computational Geometry (Spring 2020)

Last Update:

Detailed Syllabus

Notes, Labs, Assignments: These are web-access restricted links. Access those pages with name & passwd equal to the course #.

Week# Date
Notes
Topics
(high-level)
Topics
(detail)
Chapter  Assignments
Exams
Due Date

Assigns Feedback
1
J29
Notes1 Polygons & Visib Open Problems & Honors theses. Xray-guard ? Overview. 1 4Feb
1
J31
Notes2 Polygons & Visib Art Gallery Theorems. Polygon triangulation. 1
2
F5
Notes3 Polygons & Visib  Polygon triangulation: Proofs. 1
A2.pdf
(A2.zip)
A2_ans.pdf
11Feb
2
F7
Notes4 Polygons & Visib  3D Tetrahedralizations
[Skip: Scissors Congruence]
LaTeX
1
3
F12
Notes5 Polygon Triangulation Review A1.
Triangulation algorithms
Computational Complexity: big-Oh notation
1
A3.pdf
(A3.zip)
A3_ans.pdf
18Feb
3
F14
Notes6 Convex Hulls Convex Hull algorithms: 2D 2
4
F19
Notes7 Convex Hulls Review of A2
Convex Hull algorithms: 2D
2
Take Home:
A4.pdf
(A4.zip)
Includes Quiz4
Q4_ans.pdf
A4_ans.pdf
25Feb
4
F21
Notes8 Convex Hulls Review of A2 & A3; preview A4
Convex Hull algorithms: 3D
2
5
F26
Notes9 Triangulations Triangulation algorithms: Incremental, Δ Splitting
Euler's Theorem: Graph theory proof
3
No assign, but:
Suggestions
3Mar
5
F28
Notes10 Triangulations Euler's Theorem: Interdigitating trees proof
Terrain Reconstruction → Flip Graph
3
6
M4
Notes11 Triangulations Review of Q4/A4
Flip Graph
→ Delaunay Triangulation
3 3Apr
6
M6
Notes12 Triangulations Delaunay Triangulation geometry
Empty Circumcircle Property
Relation to Flipping
3
7
M11
Notes13 Voronoi Diagrams Voronoi Diagram Properties 4
7
M13
Notes14 Voronoi Diagrams VorDiags ↔ DelTri ↔ 3D Hull
Video #1
4

M18

Spring Break

Spring Break

M20

Spring Break

Spring Break

M27

Spring Break++

Spring Break++

M29

Spring Break++

Spring Break++

8
A1
Notes15 Polyhedra Five Platonic Solids
Gauss-Bonnet Thm
Videos #2,3,4,5
6
Take Home:
A6.pdf
(A6.zip)
A6_ans.pdf
10Apr
8
A3
Notes16 Polyhedra Euler's polyhedron Thm: V-E+F = 2-2g
Euler Characteristic χ = 2-2g
Hypercube; Polytopes
Videos #6,7
6
A7: Project Idea(s) & D-forms
A7.pdf
(A7.zip)
17Apr
9
A8
Notes17 Polyhedra Cauchy Rigidity Thm
Flexing Polyhedra
The Bellows Conjecture
Videos #8,9,10
6
9
A10
Notes18 Polyhedra Alexandrov's Gluing Thm
Perimeter-halving→ ∞ convex polyhedra
D-forms
Videos #11,12,13
6+new
A8: Project Progress
24Apr
10
A15
Notes19 Polyhedra D-forms : baseball stitches
A5 & A6 review
A7 preview
Latin cross re-foldings
Videos #14,15,16,17
6+new
10
A17
Notes20 Polyhedra Latin cross re-foldings
Foldings of a square
Videos #18, #19
6+new
11
A22
Notes21 Origami A7 review; A8 preview
Flat Vertex Folds
Videos #20
new
11
A24
Notes22 Origami Maekawa-Justin Thm: |M-V|=2
Kawasaki-Justin Thm: ±θi=0
Map Folding
Videos #20,21,22
new
12
A29
Notes23 Origami Shopping Bag Theorem (Rigid Origami)
Videos #23,24
new
12
M1
Notes24 Origami Fold & One-Cut Theorem
Video #25
new
13
M8
Final Project Posters
8May