Joachim Giesen, Matthias John
Proceedings of the 8th International Fall Workshop on Vision, Modeling, and Visualization
Pages 235-243, 2003
mathend000#. It is closely related to the
Delaunay triangulation. It was evident that the flow complex would be a
useful data structure for bio-geometric modeling problems. However, the input
point sets in bio-geometric modeling problems are weighted points. Thus
the theory of flow complexes needs to be extended to include weighted points.
The authors wish to extend the notion of a flow complex to that of a
weighted flow complex in order to use the flow complex as a data
structure in bio-geometric modeling.
The flow complex is basically a data structure that divides up a set of points
by defining a distance function based on those points and then classifying
regions of space based on which critical point of the distance function each
point ``flows" into. All points flow in the direction of steepest ascent (the
gradient) of the distance function.
The authors describe how to resolve the complications caused by introducing
weighted points in building a weighted flow complex. The basic problem is
that each weighted point does not necessarily correspond to a vertex of the
flow complex, but each weighted point still can influence the overall
structure of the complex. The authors then use the
weighted flow complex to decompose biological macromolecules into their
components (essentially this means that, given the set of positions of atoms
that make up a molecule, predict which pairs of atoms are bonded together) and
to give a new definition of pockets in a protein.
The authors report the results of computing the flow complex of nine different
biological molecules. It appears that the run time per atom is almost
constant: for the nine molecules, the average number of milliseconds spent per
atom are: 1.47, 2.00, 1.68, 1.74, 1.77, 1.74, 1.77, 1.82, and 1.78.
The authors believe that the definition of pockets given in this paper is more
intuitive than the earlier conventional definition.
ctj