Introduction to Computational Topology

COSC 249.09, Fall 2021

Main | Schedule | Homeworks | About

Course Schedule

Curves

9/14

When we could be diving for pearls
Fiona Ross, 2011
9 3/4” x 6”
Micron ink on Denril paper

logistics, introduction; planar curves, representations, Jordan curve/polygon theorem; winding number, representations, homotopy, invariance [lecture video|annotated slides]

• Erickson Chap 1
• Lazarus-Mesmay Sec 2.1.1
• Reference to Jordan curve theorem:
  • The Jordan-Schönflies Theorem and the Classification of Surfaces by Thomassen
  • Illustrated Proof of the Jordan Curve Theorem by Rich Schwartz, with idea from Peter Doyle
  • Algebraic Topology by Allen Hatcher, Proposition 2B.1(b)
  • Topology by Munkres, Sec 61 and 63
• Erickson Note 2
• Picture-hanging puzzles by Demaine, Demaine, Minsky, Mitchell, Rivest, and Pătrașcu

9/16

A Strange Immersion of
the Torus in 3-Space
Cassidy Curtis, 1992

regular homotopy, rotation number, Whitney-Graustein Theorem; Gauss signing, strangeness, Whitney-Graustein is tight; (smoothings, Seifert decomposition) [lecture audio|annotated slides]

• Erickson Chap 5
• Cool application of regular homotopy (no time): Mitchell-Thurston hex mesh theorem
• Untangling planar curves (shameless self-promotion)
• actual fast algorithm to compute winding numbers for 3D meshes:
  • Fast Winding Numbers for Soups and Clouds by Gavin Barill, Neil Dickson, Ryan Schmidt, David I.W. Levin, Alec Jacobson
  • Robust Inside-Outside Segmentation using Generalized Winding Numbers by Alec Jacobson, Ladislav Kavan, Olga Sorkine-Hornung

Surfaces and Complexes

9/21

Connected Holes —
Triple layered Dodecahedron
Rinus Roelofs, 2008

surfaces, triangulations, polygonal schemata, homeomorphism, classification of surfaces; surface graphs, rotation system, dual graphs [lecture video|annotated slides]

• Lazarus-Mesmay Sec 3.1 and 3.2
• Conway's ZIP proof by Franci and Weeks
• Erickson Chap 6
• Geometry Processing with Intrinsic Triangulations, Chap 2.1 and 2.2
• Comics and fun videos about surfaces:
  • Topo the World by Jean-Pierre Petit, translated by John Murphy
  • Wind and Mr. Ug by Vi Hart
• Reference to triangulation theorem:
  • The Jordan-Schönflies Theorem and the Classification of Surfaces by Thomassen

9/23

A system of loops
Weinrauch, Seidel, Mlakar,
Steinberger, Zayer, 2021

tree-cotree decomposition, system of loops, Euler's formula; Euler Calculus, curvatures and Gauss-Bonnet theorem; configuration spaces, complexes [lecture video|annotated slides]

• Erickson Chap 2.6 and 2.7
• Elementary Applied Topology by Robert Ghrist, Chap 1 to 3
• Discrete Differential Geometry: An Applied Introduction by Keenan Crane, Chap 5
• Erickson Note 10, Note 20
• Lazarus-Mesmay Sec 4.3
• Classical Topology and Combinatorial Group Theory by Stillwell, Chap 1
• Configuration spaces:
  • Hexaflexagons by Vi Hart

Linkage and Folding

9/28

Poly Bridge 2 |
My First MEGA-Project |
Overengineering
Arglin Kampling, 2020

linkage reachability and reconfiguration: polygonal chains, turning polygons inside-out, arm lemma, Cauchy-Steinitz lemma [lecture video|annotated slides]

• Geometric Folding Algorithms: Linkages, Origami, Polyhedra, Chapter 5.1.1, 5.1.2, 8.2.1, 5.3.1
• 6.849: Geometric Folding Algorithms: Linkages, Origami, Polyhedra by Erik and Martin Demaine, Fall 2020
• Universality theorem of linkages:
  • Universality theorems for configuration spaces of planar linkages by Michael Kapovich and John Millson
  • 6.849: Geometric Folding Algorithms, Lecture 9
• Carpenter's rule theorem:
  • Geometric Folding Algorithms: Linkages, Origami, Polyhedra, Chapter 6.6
  • Carpenter's Rule Theorem by Robert Connelly, Erik Demaine, Günter Rote

9/30

千羽鶴 Senbazuru
(One thousand origami cranes)

folding and origami: folding states implies motion, general foldability, Kawasaki theorem; polyhedra unfolding: polyhedrons, Steinitz theorem, Cauchy rigidity theorem, Alexandrov's theorem [lecture video|annotated slides]

• Geometric Folding Algorithms: Linkages, Origami, Polyhedra, Chapter 11.6, 13.2, 12.2, 23.1, 23.3
• Geometric Folding Algorithms: Linkages, Origami, Polyhedra, Chapter 10, 12, 14, 19, 20, 21, 22, 24. Well, you should just get the book.
• Mathematical Methods in Origami Class

Homotopy

10/5

Prentententoonstelling (Print Gallery)
M.C. Escher, 1956
Middle hole patched by
Bart de Smit and Hendrik Lenstra

testing homotopy, crossing sequence, shortest homotopic path, funnel algorithm; covering spaces, lifting, fundamental groups [lecture video|annotated slides]

• Erickson Chap 3, Chap 4
• Algebraic Topology by Allen Hatcher, Chap 1.1 and 1.3
• Classical Topology and Combinatorial Group Theory by Stillwell, Chap 1.4, 3.1-3.3
• Lazarus-Mesmay Sec 4.1

10/7

Hopf fibration with
Vysehrad railway station
Lukos Hey, 2018
oil on canvas, 60 x 90 cm

homotopy equivalence, retractions, induced homomorphisms, 2D Brouwer fixed-point theorem; computing fundamental groups, group presentations, undecidability [lecture video|annotated slides]

• Algebraic Topology by Allen Hatcher, Chap 0, 1.1, 1.2
• Lazarus-Mesmay Sec 3.4
• Classical Topology and Combinatorial Group Theory by Stillwell, Chap 4.1, 4.2.1
• Fixed Points by Vsauce
• Vietoris-Smale mapping theorem:
  • A Vietoris Mapping Theorem for Homotopy by Stephen Smale, 1957
  • Computational Algebraic Topology: Lecture Notes by Vidit Nanda, Theorem 2.12

Optimization

10/12

Loxodography
Tyler Hobbs, 2019
generative design, 16 x 20 inches

minimum (s,t)-cut in planar graphs, minimum homotopic cycle, Reif's algorithm; multiple-source shortest paths: disk-tree lemma, parametric shortest paths, red-blue lemma [lecture video|annotated slides]

• Erickson Notes 16
• Multiple-Source Shortest Paths in Embedded Graphs by Sergio Cabello, Erin W. Chambers, and Jeff Erickson, 2013
• Optimization Algorithms for Planar Graphs by Philip Klein and Shay Mozes, Chap 7
• Minimum s-t Cut of a Planar Undirected Network in O(n log^2(n)) Time, John H. Reif, 1981

10/14

Sliced Partial Optimal Transport
Nicolas Bonneel and David Coeurjolly,
SIGGRAPH 2019

r-division: BFS level cycles, fundamental-cycle separator, cycle separator, r-division through alternation; dense-distance graphs, Monge property, Monge heap, FR-Dijkstra, fast min-cut in planar graphs, planar emulator [lecture video|annotated slides]

• Erickson Notes 14 15 16 17
• Optimization Algorithms for Planar Graphs by Philip Klein and Shay Mozes
• SMAWK algorithm for fast row-minimums in a Monge matrix by Aggarwal, Klawe, Moran, Shor, Wilber, 1987.

Homology

10/19

Homologous Bones between
a Monitor lizard and an Ostrich
Grundriss der vergleichenden Anatomie,
Karl Gegenbaur, 1878

chain complex, boundary maps, cycles and boundaries, simplicial homology; computing homology, singular homology, homotopy invariance [lecture video|annotated slides]

• Computational Algebraic Topology: Lecture Notes by Vidit Nanda, Chapter 3
• Classical Topology and Combinatorial Group Theory by Stillwell, Chap 5
• Elementary Applied Topology by Robert Ghrist, Chap 4
• More rigorous treatment of homology:
  • Algebraic Topology by Allen Hatcher, Chap 2
  • Computational Algebraic Topology: Lecture Notes by Vidit Nanda, Chapter 4
• Computing homology groups using Smith normal form:
  • Edelsbrunner lecture notes, Sec IV.2 and IV.3
  • Computing Simplicial Homology Based on Efficient Smith Normal Form Algorithms by Jean-Guillaume Dumas, Frank Heckenbach, David Saunders, and Volkmar Welker, 2003

10/21

An 11-by-11 Hex Board
from The Game of Hex and the
Brouwer Fixed-Point Theorem
David Gale, 1979

Euler characteristics redux, Brouwer's fixed point theorem, relative homology, connecting map, long exact sequence; Sperner's lemma, Borsuk-Ulam theorem, ham sandwich theorem, necklace splitting theorem, fair partitioning [lecture video|annotated slides]

• Elementary Applied Topology by Robert Ghrist, Chap 5.1-5.12
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg by Jesus A. De Loera, Xavier Goaoc, Frédéric Meunier, Nabil Mustafa, Sec 1, 2, 4, 7.1
• Computational Algebraic Topology: Lecture Notes by Vidit Nanda, Chapter 4
• Using the Borsuk–Ulam Theorem by Jiří Matoušek, Chap 2-3
• Algebraic Topology by Allen Hatcher, Chap 2.B
• Game of Hex
  • Have you play the Hex game before? If not, try it here.
  • The Game of Hex and the Brouwer Fixed-Point Theorem by David Gale

Persistent Homology

10/26

Čech complex, Vietoris-Rips complex, nerve theorem, alpha complex; persistent homology, barcodes, barcode computation [no lecture video|slides]

• Barcodes: The Persistent Topology of Data by Robert Ghrist
• Computational Topology for Data Analysis by Tamal Dey and Yusu Wang, Chap 2.1-2.2, 3.1-3.3
• Computational Algebraic Topology: Lecture Notes by Vidit Nanda, Chapter 6
• Introduction to Alpha Shapes by Kaspar Fischer
• Edelsbrunner lecture notes, Sec III and IV.2
• Persistent Homology — a Survey by Herbert Edelsbrunner and John Harer
• A list of tools to compute persistent homology can be found on the course webpage by Yusu Wang

10/28

persistence diagram, bottlneck distance, stability sketching persistence diagram, applications [lecture video|annotated slides]

• Elementary Applied Topology by Robert Ghrist, Chap 5.13-5.15
• Computational Topology for Data Analysis by Tamal Dey and Yusu Wang, Chap 2.1-2.2, 3.1-3.3
• Computational Algebraic Topology: Lecture Notes by Vidit Nanda, Chapter 6
• Sketching Persistence Diagrams by Donald Sheehy and Siddharth Sheth

Morse Theory

11/2

Reeb graphs, critical points, Morse lemma, flowlines; Morse homology and inequalities, loop lemma [lecture video|annotated slides]

• Elementary Applied Topology by Robert Ghrist, Chap 7
• Morse theory by Shintaro Fushida-Hardy
• Edelsbrunner lecture notes, Sec V
• Graph Reconstruction by Discrete Morse Theory by Tamal K. Dey, Jiayuan Wang, and Yusu Wang, 2018
• Road Network Reconstruction from Satellite Images with Machine Learning Supported by Topological Methods by Tamal K. Dey, Jiayuan Wang, and Yusu Wang, 2019

11/4

discrete Morse theory: discrete gradient field, simplicial collapse, discrete flowline; evasiveness conjecture, homology lower bound on #evaders [lecture video|annotated slides]

• Elementary Applied Topology by Robert Ghrist, Chap 7.8
• A User's Guide to Discrete Morse Theory by Robin Forman, 2002
• Evasiveness of Graph Properties and Topological Fixed-Point Theorems by Carl A. Miller, 2013
• A topological approach to evasiveness by Jeff Kahn, Michael Saks, and Dean Sturtevant, 1984

Selected Topics

11/9

Intermission; ask me anything!

11/11

Presenting Almost-Linear ε-Emulators for Planar Graphs with Robert Krauthgamer and Zihan Tan, from behind the scene [lecture video|slides]

11/16

More on Borsuk-Ulam Theorem: equivalent formulations, Tucker’s Lemma, Lusternik-Schnirelmann Theorem; Kneser graphs, Lovász-Kneser Theorem, Gale’s Lemma, Schrijver graphs [lecture video|annotated slides]

• Using the Borsuk–Ulam Theorem by Jiří Matoušek, Chap 2-3
• Elementary Applied Topology by Robert Ghrist, Chap 5.8
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg by Jesus A. De Loera, Xavier Goaoc, Frédéric Meunier, Nabil Mustafa, Sec 1-2

Topics we might not get to cover

3-manifolds: knots, normal surface theory

low-distortion routing: multi-commodity flows, L1 embeddings, planar embedding conjecture

topological graph theory: planar covers and Negami 1-2-infinity conjecture, theory of almost-planar graphs

combinatorics of curves: pseudolines, self-overlapping curves, electrical moves, Hanani-Tutte, weak embeddings

planar graph algorithms: disjoint paths, multi-terminal flows and cuts, diameter, matchings, distance oracles

differential topology: transversality, genericity, intersection theory

geometric topology: mapping class group, Dehn twists, Lickorish generators

tools on planar graphs: Tutte spring embedding, Maxwell–Cremona correspondence, Schnyder woods

shape analysis: Mapper and friends