2
$\begingroup$

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

$\endgroup$
9
  • 2
    $\begingroup$ What do you mean by "typical"? One which everyone is considering? One which everyone uses as an example? One which motivated the subject? One that your lecturer works on? etc. $\endgroup$ – Yemon Choi Oct 27 '11 at 22:34
  • 1
    $\begingroup$ One which everyone uses as an example $\endgroup$ – user695652 Oct 27 '11 at 23:15
  • 1
    $\begingroup$ I don't know about tagging this computational-geometry, so I"m adding a computational-topology tag $\endgroup$ – theHigherGeometer Oct 27 '11 at 23:44
  • 3
    $\begingroup$ The Stanford group has a preprints page. Go there, there's many good examples. For example: A. Zomorodian and G. Carlsson, “Localized homology” , Shape Modeling International , Lyon, France . Jan 2007 link $\endgroup$ – Ryan Budney Oct 28 '11 at 14:33
  • 3
    $\begingroup$ Your question is rather confusing. The answer you accepted gives an example paper which is very much not of the sort you requested. $\endgroup$ – Ryan Budney Nov 24 '11 at 22:33
4
$\begingroup$

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.
            Fig3

$\endgroup$
2
  • $\begingroup$ This is nice. It harks back to the early days of Riemann surfaces, when 'connectedness' (=genus) was defined by curves along which one cut the surface. $\endgroup$ – theHigherGeometer Oct 28 '11 at 0:56
  • $\begingroup$ Thanks you for the nice paper suggestion, that was what I was looking for. $\endgroup$ – user695652 Oct 28 '11 at 15:36
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.