Welcome to MathOverflow

Question

0

2

Hi

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

edited Oct 27 2011 at 23:44

David Roberts
11.7k●2●18●55

asked Oct 27 2011 at 22:19

andy
309●1●5

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. – Yemon Choi Oct 27 2011 at 22:34

1

One which everyone uses as an example – andy Oct 27 2011 at 23:15

I don't know about tagging this computational-geometry, so I"m adding a computational-topology tag – David Roberts Oct 27 2011 at 23:44

It really depends on the flavour of computational topology you're interested in. For example, computational 3-manifold topology -- things like the 3-sphere recognition algorithm -- have a very different flavour than say the Edelsbrunner / Harer text. – Ryan Budney Oct 27 2011 at 23:49

1

Oh thanks I wasn't aware of this. Yes I meant more the Edelsbrunner type. – andy Oct 27 2011 at 23:50

show 4 more comments

Joseph O'Rourke · Accepted Answer · 2011-10-27 23:53:00Z UTC

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

yogesh · Answer 2 · 2011-11-24 22:10:43Z UTC

2

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.

answered Nov 24 2011 at 22:10

yogesh
101●4

Computational Topology Paper

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.