Algorithms for the Reeb Graph and Related Concepts

dc.contributor.advisor

Edelsbrunner, Herbert

dc.contributor.author

Parsa, Salman

dc.date.accessioned

2015-01-28T18:10:08Z

dc.date.available

2015-01-28T18:10:08Z

dc.date.issued

2014

dc.department

Computer Science

dc.description.abstract

This thesis is concerned with a structure called the Reeb graph. There are three main problems considered. The first is devising an efficient algorithm for comnstructing the Reeb graph of a simplicial complex with respect to a generic simplex-wise linear real-valued function. We present an algorithm that builds the Reeb graph in almost optimal worst-case deterministic time. This was the first deterministic algorithm with the time bound which is linear up to a logarithmic factor. Without loss of generality, the complex is assumed to be 2-dimensional. The algorithm works by sweeping the function values and maintaining a spanning forest for the preimage, or the level-set, of the value. Using the observation that the operations that change the level-sets are off-line, we was able to achieve the above bound.

The second topic is the dynamic Reeb graphs. As the function changes its values, the Reeb graph also changes. We are interested in updating the Reeb graph. We reduce this problem to a graph problem that we call retroactive graph connectivity. We obtain algorithms for dynamic Reeb graphs, by using data structures that solve the graph problem.

The third topic is an argument regarding the complexity of computing Betti numbers. This problem is also related to the Reeb graph by means of the vertical Homology classes. The problem considered here is whether the realization of a simplicial complex in the Euclidean 4-space can result in an algorithm for computing its Homology groups faster than the usual matrix reduction methods. Using the observation that the vertical Betti numbers can always be computed more efficiently using the Reeb graph, we show that the answer to this question is in general negative. For instance, given a square matrix over the field with two elements, we construct a simplicial complex in linear time, realized in euclidean 4-space and a function on it, such that its Horizontal homology group, over the same field, is isomorphic with the null-space of the matrix. It follows that the Betti number computation for complexes realized in the 4-space is as hard as computing the rank for a sparse matrix.

dc.identifier.uri

https://hdl.handle.net/10161/9422

dc.subject

Computer science

dc.subject

Mathematics

dc.subject

algorithms

dc.subject

Betti number computation

dc.subject

dynamic algorithms

dc.subject

graph connectivity

dc.subject

offlice graph connectivity

dc.subject

Reeb graph

dc.title

Algorithms for the Reeb Graph and Related Concepts

dc.type

Dissertation

Files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
Parsa_duke_0066D_12682.pdf
Size:
766.41 KB
Format:
Adobe Portable Document Format

Collections