I am delving into the field of Computational Topology. I am aware of the books in this field, but could anybody tell me a nice relevant paper in this field which tackles a "typical" Computational Topology problem?
Thank you
MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this communityI am delving into the field of Computational Topology. I am aware of the books in this field, but could anybody tell me a nice relevant paper in this field which tackles a "typical" Computational Topology problem?
Thank you
Perhaps the paper by Jeff Erickson and Pratik Worah,
"Computing the Shortest Essential Cycle,"
Discrete & Computational Geometry,
Volume 44, Issue 4, December 2010 (PDF link),
might serve your purposes.
They compute the shortest
"simple cycle that cannot be continuously deformed to a point or a single boundary."
The input to their problem
is "a combinatorial surface, which is an abstract topological surface $M$ together with an edge-weighted graph $G$ cellularly embedded on $M$."
If $n$ is the complexity of the surface, their algorithm runs in $O(n^2 \log n)$ time,
and faster, $O( n \log n)$, when the genus and number of boundaries are considered fixed.
This paper is, in some sense, a culmination of a series of papers finding cycles on combinatorial
surfaces, often to cut them along the cycles to produces simpler surfaces.
The interesting books i know of are Edelsbrunner/Harer and Zomordian's thesis. On similar topics, the Comtop group at Stanford has very detailed information.