Feb. 11, 2004

BACK

Publications in Computational Topology by Herbert Edelsbrunner et al. :

• Morse-Smale complexes for piecewise linear 3-manifolds, 2003.
• Loops in Reeb Graphs of 2-Manifolds, 2003.
• Hierarchical Morse complexes for piecewise linear 2-manifolds, 2001.
• Emerging Challenges in Computational Topology, 1999.
• Computational Topology, 1998.
• Auditory Morse analysis of triangulated manifolds, 1998.
• Triangulating Topological Spaces, 1997.

BibTeX references.

Other related papers on Computational Geometry (link):

• Three-dimensional alpha shapes, 1994.
• Delaunay and Regular Triangulation in Space, 1993.
• On the shape of a set of points in the plane, 1983.

Other related papers on Computational Chemistry (link):

• On the definition and the construction of pockets in macromolecules, 1998.
• Analytic shape computation of macromolecules I: Molecular area and volume through alpha shape, 1998.
• Analytic shape computation of macromolecules II: Inaccessible cavities in proteins, 1998.

Raindrop Geomagic, Inc. : www.geomagic.com:
Company co-founder

We define the Morse-Smale complex of a Morse function over a 3-manifold as the overlay of the descending and ascending manifolds of all critical points. In the generic case, its 3-dimensional cells are shaped like crystals and are separated by quadrangular faces. In this paper, we give a combinatorial algorithm for constructing such complexes for piecewise linear data.

Given a Morse function 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.

We present algorithms for constructing a hierarchy of increasingly coarse Morse complexes that decompose a piecewise linear 2-manifold. While Morse complexes are defined only in the smooth category, we extend the construction to the piecewise linear category by ensuring structural integrity and simulating differentiability. We then simplify Morse complexes by cancelling pairs of critical points in order of increasing persistence.

Keywords: Computational topology, PL manifolds, Morse theory, topological persistence, hierarchy, algorithms, implementation, terrains

Web link: http://www.cis.ohio-state.edu/~tamaldey/computopo.html

Web link: http://citeseer.nj.nec.com/dey99computational.html

The authors of this article believe there is or should be a research area appropriately referred to as computational topology. Its agenda includes the identification and formalization of topological questions in computer applications and the study of algorithms for topological problems. It is hoped this article can contribute to the creation of a computational branch of topology with a unifying influence on computing and computer applications.

Keywords. Survey; topology, geometry, algorithms, computer applications.

Weblink: http://www.cs.duke.edu/~edels/TriTop/

Given a subspace X subseteq R^d and a finite set S subeseteq R^d, we introduce the Delaunay simplicial complex, D_X, restricted by X. Its simplices are spanned by subsets T \subeseteq S for which the common intersection of Voronoi cells meets X in a non-empty set. By the nerve theorem, \bigcup DX and X are homotopy equivalent if all such sets are contractible. This paper shows that \bigcup DX and X are homeomorphic if the sets can be further subdivided in a certain way so they form a regular CW complex.

BACK

Page created & maintained by Frederic Leymarie, 2001-4.
Comments, suggestions, etc., mail to: leymarie@lems.brown.edu