One-Dimensional Computational Topology

CS 598 JGE, Fall 2020

Announcements

Dec 21

Project presentation videos are now available. And that's it for the semester!

Dec 8

Final project presentations have been scheduled the following days and times:

1–3pm on Monday, December 14
10-noon on Wednesday, December 16
1-3pm on Thursday, December 17

Check this web page and/or your email for your group's assigned date and time. There will be four 20-minute presentations in each time slot. The schedule page is password protected; use the same credentials as the Paper Chase submissions and project submissions.

Nov 29

Because of the pandemic, all course evaluations are now being solicited thorugh ICES Online. Evaluations forms for this class are available through Thursday, December 10. Please fill out an evaluation form; your feedback is extremely important, especially narrative feedback. (Please submit evaluations for all your other courses as well!)

Nov 23

Final project logistics:

As a reminder, groups of up to three students can submit a single joint project. Please register your project groups by filling out this web form no later than Monday, December 7. This is a hard deadline! Only one person in each group should submit the form.
Each group will give a 20–30 minute presentation on their project during finals week. (The exact length will depend on the number of registered projects.) I plan to schedule all presentations within a few two-hour windows, so that as many people as possible can participate at the same time. The form asks each group to rank times when they would lie to present, and indicate times when they cannot present. I will announce the presentation times (and duration) in class on Tuesday, December 8.
Project reports are due Wednesday, December 9, the last day of instruction for the fall semester. Each project group should submit a single PDF to Gradescope. Whoever submits the report should also tell Gradescope who the other group members are; please also list all group members on the first page of the report.

Nov 5

Video of yesterday's presentation of all project proposals is available on a restricted MediaSpace channel, which is accessible only to registered students (via Shibboleth). Videos of final project presentations will eventually be posted to the same channel.

Nov 4

Everyone's project proposals are available, again only to registered students. Use the same credentials as the Paper Chase submissions.

Oct 23

Everyone's submissions for the Paper Chase assignment are available, but only to registered students. Check your email for the password. (Hint: Seven spaces.)

Oct 5

Project proposals are due Friday, October 30. This is a hard deadline! Each student submits their own individual 2-to-3-page proposal.

Submit your proposal as a pdf file on Gradescope.

Sep 1

The first writing assignment is due September 21.

Submit your writeup as a single pdf file on Gradescope; you can enroll yourself with code 96BXXV.
You may find my computational topology bibliography useful; this is a bibtex file listing almost 2000 references (about half published in the last 25 years). I'm sure your favorite papers are missing.

Aug 31

By now all registration restrictions should have been lifted. If you are still unable to register by Wednesday, September 2, please send me email and post a direct message on CampusWire. Yes. even if you've already done that.
I have changed my class office hours to Friday 9-10 to accommodate studnets taking the class from China. I've also moved my public office hours one our earlier, to Wednesday and Friday 3-4pm, to avoid a collision with the regular theory-student social hour. Please come say hi!

Aug 17

Hello and welcome! I'm still setting up the class; please forgive the dust, construction noises, and dead links. First some logistics:

Currently the class is formally restricted to computer science graduate students, but these registration restrictions should be removed by August 28. If you are still unable to register by the beginning of the first week (August 31), please send me email and post a message to Campuswire.
At least for the first several weeks, I will give synchronous lectures over Zoom at the scheduled class time (TuTh 11:00–12:15). Please make an effort to attend "live"; lectures are much more interesting for everyone if people ask questions! All lectures will be recorded; video will be available shortly after each class meeting.
We are using CampusWire as an online discussion forum. You can enroll yourself with the code 4637. (CampusWire is the campus-ordained replacement for Piazza, which apparently suffers from some unfixable FERPA-related issues.)
I plan to maintain a list of "homework" exercises. These are meant only for your practice and understanding; homework will not be graded. I strongly encourage discussing these exercises (and any similar problems that occur to you) on CampusWire.

About this class

This course will be an introduction to my favorite facet of computational topology: Algorithms for curves and graphs embedded in the plane or other surfaces. Algorithmic questions about curves have been a driving force in topology since its inception more than a century ago. Planar and near-planar graphs have long been fertile ground for algorithms research, both because they naturally model many classes of networks that arise in practice, and because they admit simpler and faster algorithms than more general graphs. There is a rich interplay between these two domains, drawing on a common pool of techniques from geometry, topology, and combinatorics. Potential topics include topological graph theory; homotopy, homology, and other topological invariants; specialized algorithms for shortest paths, maximum flows, and minimum cuts; efficient approximation schemes for NP-hard problems; and applications in VLSI design, computer graphics, computer vision, motion planning, geographic information systems, and other areas of computing. Specific topics will depend on the interest and expertise of the students.

Students in all areas of computer science, mathematics, and related disciplines are welcome. CS 473 and/or Math 525 are recommended as prerequisites, but not required; necessary background material will be introduced as needed. Undergraduates interested in taking this course can get a registration override at the first lecture.

Historical Gallery

A Möbius-band chain pump. Al-Jazari, Book of Knowledge of Ingenious Mechanical Devices (1206)

Nonagonus secundi ordinis. Thomas Bradwardine, Geometria speculativa (c.1320)

The first maze. Giovanni Fontana, Bellicorum instrumentorum liber cum figuris (c.1420)

An unfolding of a snub cube. Albrecht Dürer, Underweysung der messung (1520)

A tree of forces in equilibrium. Simon Stevin, Byvough der Weeghconst [Supplement to The Art of Weighing] (1605)

Lifting the (punctured) disk to a helical screw. Henrik Stevin, Plaetboec vervangende de figuren of formen gehorig tottet Wisconstich filosofisch bedryf (1668)

The first(?) reciprocal force diagram. Pierre Varignon, Nouvelle mecanique ou Statique (1725)

Computing the area of a non-convex polygon. Albrecht Meister, Generalia de genesi figurarum planarum et inde pendentibus earum affectionibus (1770)

A simple closed curve. Bernard Bolzano, Die drey Probleme der Rectification, der Complanation und der Cubirung (1817)

Decomposing a non-simple curve into simple curves. Carl Friedrich Gauß, Zur Geometria situs (Nachlass) (c.1830)

Proving that every convex(!) polygon can be triangulated. Carl Friedrich Gauß, Zur Geometria situs (Nachlass) (c.1830)

A system of cycles and its dual system of arcs on a punctured torus. Bernhard Riemann, Theorie der Abel'schen Functionen (1857)

A pants decomposition. Johann Benedict Listing, Census Räumlicher Complexe (1862)

"Alexander" numbering of a nonsimple polygon. Johann Benedict Listing, Vorstudien von Topologie (1847)

Cutting a surface at non-critical heights. August Möbius, Theorie dr elementaren Verwandtschaft (1863)

A reciprocal pair of form/force diagrams. James Clerk Maxwell, On reciprocal figures and diagrams of forces (1864)

Flipping an edge in a triangulation. August Möbius, Ueber die Bestimmung des Inhalts eines Polyëders (1865)

The "Morse-Smale" complex of a smooth terrain. James Clerk Maxwell, On Hills and Dales (1870)

A planar map and its dual, specified by the same rotation system. Max Brückner, Vielecke und Vielflache: Theorie und Geschichte (1900)

Paul Klee, Pedagocial Sketchbook (1925), English translation by Sybil Moholy-Nagy (1953)

The "tree-onion figure" of a planar map. Max Dehn, Über kombinatorische Topologie (1936)

Piet Hein's inspirations for the game "Polygon", now known as "Hex". Piet Hein, "Vil de lære Polygon?", Politiker (December 26, 1942)

Asteroids, developed by Lye Raine, Ed Logg, and Dominic Walsh (1979)

Other computational topology classes

The selection of topics in this class is necessarily limited by the finiteness of a single semester and by my own interests and expertise. Important topics in computational topology that I will not cover this semester, except perhaps briefly in passing, include automatic groups, knot theory, 3-manifolds, cell complexes (simplicial, cubical, Delta, CW, simplicial sets), discrete Morse theory, normal surface theory, configuration spaces, dynamical systems, persistent homology and its generalizations, surface reconstruction, manifold learning, topological data analysis, embedding obstructions, higher-order homotopy, discrete differential geometry, fixed-point theorems, applied Hodge theory, algebraic complexity, evasiveness of graph properties, impossibility results in distributed computing, and topological quantum computing. The full diversity of techniques, results, applications, and even definitions of computational topology could easily fill a dozen courses.

Here is an incomplete (and rather outdated) list of other recent courses in computational topology with publicly available course materials (beyond just a syllabus). Please let me know if you'd like to add your course!