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
$\begingroup$
$\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 ChoiCommented Oct 27, 2011 at 22:34
-
1$\begingroup$ One which everyone uses as an example $\endgroup$– user695652Commented Oct 27, 2011 at 23:15
-
1$\begingroup$ I don't know about tagging this computational-geometry, so I"m adding a computational-topology tag $\endgroup$– David Roberts ♦Commented Oct 27, 2011 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 BudneyCommented Oct 28, 2011 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 BudneyCommented Nov 24, 2011 at 22:33
|
Show 4 more comments
2 Answers
$\begingroup$
$\endgroup$
2
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.
answered Oct 27, 2011 at 23:53
-
$\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$– David Roberts ♦Commented Oct 28, 2011 at 0:56
-
$\begingroup$ Thanks you for the nice paper suggestion, that was what I was looking for. $\endgroup$ Commented Oct 28, 2011 at 15:36
$\begingroup$
$\endgroup$
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.
