The Flow Complex: A Data Structure for Geometric Modeling

Joachim Giesen, Matthias John

Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA)

Pages 285-294, 2003

Motivation

Many applications require structuring finite sets of points. For example, the set of points sampled from a surface by a laser range scanner, or the set of centers of atoms in a protein, are finite sets of points that one might wish to structure, even though the points themselves often come unstructured.

Goal of This Research

The authors wish to structure a given point cloud into a simplicial complex like the Delaunay triangulation, but which may be more suitable for certain types of point clouds and is still efficient to compute.

Goal of This Paper

The authors introduce the flow complex, a simplicial complex that can be computed efficiently from a finite set of points. The flow complex of a finite set of points P mathend000# in 1#1³ mathend000# is constructed as follows. First define a distance function h : 1#1³2#21#1 mathend000# where h(x) mathend000# is the minimum distance from x mathend000# to any point in P mathend000#. This function has a direction of steepest ascent everywhere except at its critical points. Now we imagine that all points in 1#1³ mathend000# ``flow" in the direction of steepest ascent of h mathend000#. It turns out that every point in 1#1³ mathend000# flows into either a critical point of h mathend000# or to infinity. We can cluster the points P mathend000# together based on which point they flow into, and this idea eventually leads to a triangulation of the points P mathend000#.

Related Work

Results

The authors found that the flow complex is well suited for reconstructing the surface from which a finite set of points was sampled. Also the authors use the flow complex to model pockets in proteins in a way that is similar to earlier work that modeled pockets using the Delaunay triangulation. The authors claim however that the definition of pockets using the flow complex is easier to understand.

The authors do not yet have a tight bound on the time complexity for computing the flow complex of n mathend000# points, although there is a trivial O(n⁶) mathend000# upper bound. In two dimensions, the space complexity of the flow complex 3#3(n²) mathend000# which is worse than the Delaunay triangulation's 3#3(n) mathend000# complexity.

Bibliography