448
COMPUTATIONAL TOPOLOGY AND GEOMETRY (SPRING 2025)
- Instructor
-
- Jonathan Pakianathan
- E-mail: jonathan.pakianathan@rochester.edu
- Office: Hylan 809
- Class Meetings:
-
MW 12:30-13:45PM in room Hylan 1106A.
- Office Hours:
-
Wed, 1:50PM-2:50PM (right after class) in Hylan 809.
-
Thur, noon-1 PM in Hylan 809.
- Primary Textbook:
-
Computational Topology, by H. Edelsbrunner and J. Harer. ISBN-13: 978-0821849255
-
Link to amazon site for the book: https://www.amazon.com/Computational-Topology-Introduction-Herbert-Edelsbrunner/dp/0821849255
-
A link to a free pdf is here: https://www.maths.ed.ac.uk/~v1ranick/papers/edelcomp.pdf
-
This book is skimpy on details for the earlier topics so we will supplement with some nice notes by Jeff Ericksen for the first part of the course in the week by week learning modules on the course Blackboard.
- Supplementary Textbooks:
- (not required - do not worry if you don’t know differential or algebraic topology before the course - we’ll only need some parts which will be discussed in class)
-
Topology, by James R. Munkres, 2nd edition (2000). ISBN:0-13-181629-2
-
Differential Topology, by Victor Guillemin and Alan Pollack, (1974). ISBN:0-13-212605-2
-
Here is a link for Erickson’s general algorithms book that can also be useful in the beginning: http://jeffe.cs.illinois.edu/teaching/algorithms/book/Algorithms-JeffE.pdf in understanding time efficiency of various algorithms.
-
Elements of Algebraic Topology, by James R. Munkres, 2nd edition (2025). ISBN 9781032765549.
-
Discrete and Computational Geometry, by S. Devadoss and J. Rourke, (2011). ISBN: 978-0-691-14553-2.
- Course Description:
-
Computational topology and Computational Geometry are an emerging field of study at the intersection of mathematics and computer science.
-
This course will sample a collection of problems that involve various aspects of topology and geometry in important applications. Most people are aware of the many useful algorithms involving graphs, one of the simplest types of 1-dimensional object - in this course we will focus on higher dimensional applications but no prior experience in algorithms is necessary. The course will be structured so that those who wish to focus on computing issues can blackbox a lot of the topology and vice versa - homeworks will be written so students can select which problems to do in a way that enables both types of focus.
-
We will start off reviewing basic paradigms from numerical analysis regarding robustness of algorithms(how sensitive are processes like extracting the roots of a polynomial, solving a linear system or doing a least squares linear regression to variations/errors in the inputs) and recap the time efficiency analysis of basic mathematical algorithms and recursion tree analysis before proceeding to the geometric algorithms forming the core of the course.
-
Geometric algorithms covered include efficient computations of convex and affine hulls in low dimension, Voronoi cells and Delaunay triangulations with consequent applications to topographical reconstruction (curve and surface reconstruction.)
-
We will also explore the use of simplicial complexes, the topology of cell complexes, homotopy and simplicial homology with applications to topological data analysis including persistent homology of large data sets, topological tomography and network converage.
-
Configuration spaces, robotic motion planning, image processing, discrete Morse theory and normal surface theory algorithms will also be explored as time permits.
-
There will be some overlap with a similar course given in Fall 2024 by the Computer Science Department in the first part but we will eventually shift to applications that are different than those covered there.
- Prerequisites:
-
MTH 265 (real analysis) or MTH240 (undergraduate topology) or equivalent.
-
Multivariable calculus and linear algebra.
-
Some familiarity with basic algorithms like search and sort algorithms is nice but not assumed. We’ll provide self contained development though occasionally a student would have to blackbox a fact that would have been proven or covered in a different course but references will be provided in these cases.
- Course Components:
-
The course will be graded out of 100 points. 72 points will come from 6 homework sets worth 12 points each, 28 points from the course final. For more information on these components see below.
- Final (28 course points=28%)
-
The final will be on TBA in TBA.
-
No books, notes or electronics may be used during the exam.
- Homework (72 course points=72%)
-
Homework will be posted here and in the relevant weekly learning module on Blackboard. Written homework will be due on Gradescope on Saturdays at 11:59PM and occur every 2-3 weeks. The first graded homework set HW1 is due TBA. There will be 6 homework sets in total worth 12 points each. In each you only have to answer a selection of homework questions and not all of them - there will be homework that covers theoretical, computational and algorithmic aspects of the course. No programming is necessary though some questions will give you the option to explore certain topics on Matlab, Mathematica or other computer implementations of your choice. If you prefer to not do this, there will be ample questions to select from that require no programming or computer use.
-
You may collaborate on homework and consult books and online resources while working on a problem but must write up the final solution in your own words and on your own (thus you should internalize the solution you find collaboratively so that when writing it up, you do not consult any other sources.) Under no circumstance should you use any homework services such as Cheggs.com in any manner to directly help on homework or exams during the course - any such usage is a severe violation of academic honesty.
HOMEWORK GRADERS:
- Academic Integrity Statement
-
You are responsible for knowing and abiding by the University of Rochester’s academic integrity code. For a complete listing, visit the College’s web site. Any violation of academic integrity will be pursued according to the specified procedures.
-
Department of Mathematics policy on unauthorized online resources: Any usage whatsoever of online solution sets or paid online resources (chegg.com or similar) is considered an academic honesty violation and will be reported to the Board on Academic Honesty. In particular, any assignment found to contain content which originated from such sources is subject to a minimum penalty of zero on the assignment and a full letter grade reduction at the end of the semester (e.g. a B would be reduced to a C). This applies even if the unauthorized content was obtained through indirect means (through a friend for instance) and/or the student is seemingly unaware that the content originated from such sources. If you have any questions about whether resources are acceptable, please check with your instructor.
- College Credit-Hour Policy:
-
This course follows the College credit hour policy for four-credit courses. This course meets 3 academic hours per week. Students may also be expected to deepen their understanding of the course material through close examination/evaluation of the readings assigned in the course.