Schnelleinstieg Reader


Startseite FSU

A Parallel Algorithm for Computing the Flow Complex

We have implemented a parallel algorithm for computing the entire Hasse diagram of the flow complex of point cloud data in Euclidean space. Known algorithms for computing the flow complex in two and three dimensions compute the geometric realization of the flow complex and need to compute the Delaunay triangulation of the point cloud data first. Our algorithm computes less information, namely only the Hasse diagram of the flow complex that has been augmented with enough geometric information to allow the same topological multi-scale analysis of point cloud data as with alpha shapes. The algorithm avoids the explicit computation of the Delaunay triangulation.

More information on the algorithm and its implementation can be found in our paper:

  • J. Giesen and L. Kühne. A parallel algorithm for computing the flow complex. Proceedings of the 28th Annual ACM Symposium on Computational Geometry (SoCG), (2013)

You can download the code of our C++ implementation here.