TY - JOUR
AB - We combine topological and geometric methods to construct a multiresolution representation for a function over a two-dimensional domain. In a preprocessing stage, we create the Morse-Smale complex of the function and progressively simplify its topology by cancelling pairs of critical points. Based on a simple notion of dependency among these cancellations, we construct a hierarchical data structure supporting traversal and reconstruction operations similarly to traditional geometry-based representations. We use this data structure to extract topologically valid approximations that satisfy error bounds provided at runtime.
AU - Bremer, Peer-Timo
AU - Herbert Edelsbrunner
AU - Hamann, Bernd
AU - Pascucci, Valerio
ID - 3984
IS - 4
JF - IEEE Transactions on Visualization and Computer Graphics
TI - A topological hierarchy for functions on triangulated surfaces
VL - 10
ER -
TY - JOUR
AB - Given a Morse function f over a 2-manifold with or without boundary, the Reeb graph is obtained by contracting the connected components of the level sets to points. We prove tight upper and lower bounds on the number of loops in the Reeb graph that depend on the genus, the number of boundary components, and whether or not the 2-manifold is orientable. We also give an algorithm that constructs the Reeb graph in time O(n log n), where n is the number of edges in the triangulation used to represent the 2-manifold and the Morse function.
AU - Cole-McLaughlin, Kree
AU - Herbert Edelsbrunner
AU - Harer, John
AU - Natarajan, Vijay
AU - Pascucci, Valerio
ID - 3985
IS - 2
JF - Discrete & Computational Geometry
TI - Loops in Reeb graphs of 2-manifolds
VL - 32
ER -
TY - JOUR
AB - The motion of a biomolecule greatly depends on the engulfing solution, which is mostly water. Instead of representing individual water molecules, it is desirable to develop implicit solvent models that nevertheless accurately represent the contribution of the solvent interaction to the motion. In such models, hydrophobicity is expressed as a weighted sum of atomic surface areas. The derivatives of these weighted areas contribute to the force that drives the motion. In this paper we give formulas for the weighted and unweighted area derivatives of a molecule modeled as a space-filling diagram made up of balls in motion. Other than the radii and the centers of the balls, the formulas are given in terms of the sizes of circular arcs of the boundary and edges of the power diagram. We also give inclusion-exclusion formulas for these sizes.
AU - Bryant, Robert
AU - Herbert Edelsbrunner
AU - Koehl, Patrice
AU - Levitt, Michael
ID - 3986
IS - 3
JF - Discrete & Computational Geometry
TI - The area derivative of a space-filling diagram
VL - 32
ER -
TY - JOUR
AB - We consider scientific data sets that describe density functions over three-dimensional geometric domains. Such data sets are often large and coarsened representations are needed for visualization and analysis. Assuming a tetrahedral mesh representation, we construct such representations with a simplification algorithm that combines three goals: the approximation of the function, the preservation of the mesh topology, and the improvement of the mesh quality. The third goal is achieved with a novel extension of the well-known quadric error metric. We perform a number of computational experiments to understand the effect of mesh quality improvement on the density map approximation. In addition, we study the effect of geometric simplification on the topological features of the function by monitoring its critical points.
AU - Natarajan, Vijay
AU - Herbert Edelsbrunner
ID - 3987
IS - 5
JF - IEEE Transactions on Visualization and Computer Graphics
TI - Simplification of three-dimensional density maps
VL - 10
ER -
TY - CONF
AB - We give an algorithm that locally improves the fit between two proteins modeled as space-filling diagrams. The algorithm defines the fit in purely geometric terms and improves by applying a rigid motion to one of the two proteins. Our implementation of the algorithm takes between three and ten seconds and converges with high likelihood to the correct docked configuration, provided it starts at a position away from the correct one by at most 18 degrees of rotation and at most 3.0Angstrom of translation. The speed and convergence radius make this an attractive algorithm to use in combination with a coarse sampling of the six-dimensional space of rigid motions.
AU - Choi, Vicky
AU - Agarwal, Pankaj K
AU - Herbert Edelsbrunner
AU - Rudolph, Johannes
ID - 3988
TI - Local search heuristic for rigid protein docking
VL - 3240
ER -