afra
zomorodian

 home
personal
book
papers
teaching
goodies


  
BibTeX for all publications
  Computational Topology
Algorithms and Theory of Computation Handbook, 2009.

According to the Oxford English Dictionary, the word topology is derived of topos (τοπος) meaning place, and -logy (λογια), a variant of the verb λεγειν, meaning to speak. As such, topology speaks about places: how local neighborhoods connect to each other to form a space. Computational topology, in turn, undertakes the challenge of studying topology using a computer.

This is chapter for the second edition of the handbook, edited by Mikhail J. Atallah and Marina Blanton.


  Colon Polyp Detection using Smoothed Shape Operators: Preliminary Results. with Padma Sundaram, Christopher Beaulieu, and Sandy Napel.
Medical Image Analysis, 2008. – doi:10.1016/j.media.2007.08.001

Computer-aided detection (CAD) algorithms identify locations in Computed Tomographic (CT) images of the colon that are most likely to contain polyps. In this paper, we present the Smoothed Shape Operators method (SSO), which uses a geometry processing approach. We extract a triangle mesh representation of the colon surface, and estimate curvature on this surface using the shape operator. We then smooth the shape operators on the surface iteratively. We evaluate our algorithm on patient data and provide free-response receiver operating characteristic performance analysis over all size ranges of polyps. We also provide confidence intervals for our performance estimates. We compare our performance with the Surface Normal Overlap (SNO) method for the same data.

  On the Local Behavior of Spaces of Natural Images. with Gunnar Carlsson, Tigran Ishkhanov, and Vin de Silva.
International Journal of Computer Vision, 2008. (ps.gz) – doi:10.1007/s11263-007-0056-x

In this study, we concentrate on qualitative topological analysis of the local behavior of the space of natural images. To this end, we use a space of 3 by 3 high-contrast patches M studied by Mumford et al. We develop a theoretical model for the high-density 2-dimensional submanifold of M showing that it has the topology of the Klein bottle. Using our topological software package PLEX we experimentally verify our theoretical conclusions. We use polynomial representation to give coordinatization to various subspaces of M. We find the best-fitting embedding of the Klein bottle into the ambient space of M. Our results are currently being used in developing a compression algorithm based on a Klein bottle dictionary.

  Persistent voids: a new structural metric for membrane fusion. with Peter M. Kasson, Sanghyun Park, Nina Singhal, Leonidas J. Guibas, and Vijay S. Pande.
Bioinformatics, 2007. (ps.gz) – doi:10.1093/bioinformatics/btm250

Membrane fusion constitutes a key stage in cellular processes such as synaptic neurotransmission and infection by enveloped viruses. We introduce a novel structural measurement of vesicle topology and fusion geometry: persistent voids. We use persistent voids to compute dynamic relationships between hemifusion neck widening and formation of a full fusion pore in our simulation data. Our findings suggest that rapid fusion between small vesicles proceeds via a small hemifusion diaphragm rather than a full-expanded one.

  Localized Homology. with Gunnar Carlsson.
Computational Geometry: Theory & Applications, 2008. (ps.gz) – doi:10.1016/j.comgeo.2008.02.003
Shape Modeling International, Lyon, France, 2007. (ps.gz)
Supplemental package: Localizing within a 3D Solid

In this paper, we provide a complete theoretical foundation and an effective algorithm for localizing topological attributes. Unlike previous work that focused on 2-manifolds with restricted geometry, our theory is general and localizes arbitrary-dimensional attributes in arbitrary spaces. We implement our algorithm to validate our approach in practice.

  The Theory of Multidimensional Persistence. with Gunnar Carlsson.
23rd ACM Symposium on Computational Geometry, Gyeongju, South Korea, 2007. (ps.gz)
Discrete and Computational Geometry, 2009 (Invited). (ps.gz) – doi:10.1007/s00454-009-9176-0

Persistent homology captures the topology of a filtration – a one-parameter family of increasing spaces – in terms of a complete discrete invariant. This invariant is a multiset of intervals that denote the lifetimes of the topological entities within the filtration. In many applications of topology, we need to study a multifiltration: a family of spaces parameterized along multiple geometric dimensions. In this paper, we show that no complete discrete invariant exists for multidimensional persistence. We also propose a discrete invariant, the rank invariant, for the robust estimation of Betti numbers in a multifiltration, and prove its completeness in one dimension.

  Geometric Filtering of Pairwise Atomic Interactions Applied to the Design of Efficient Statistical Potentials. with Leonidas J. Guibas and Patrice Koehl.
Computer Aided Geometric Design, 2006. (ps.gz) – doi:10.1016/j.cagd.2006.03.002

Distance-dependent, pairwise, statistical potentials are based on the concept that the packing observed in known protein structures can be used as a reference for comparing different 3D models for a protein. We show that we can filter the list of all interactions in a protein to generate a much smaller subset of pairs that retains most of the structural information contained in proteins.

  The Conformal Alpha Shape Filtration. with Frederic Cazals, Joachim Giesen, and Mark Pauly.
The Visual Computer, 2006. (ps.gz) – doi:10.1007/s00371-006-0027-1
Symposium on Point-Based Graphics, Stony Brook, NY, 2005. (ps.gz)

We define a new filtration of the Delaunay triangulation of a finite set of points in Rd, similar to the alpha shape filtration. The new filtration is parameterized by a local scale parameter instead of the global scale parameter in alpha shapes. Since our approach shares many properties with the alpha shape filtration and the local scale parameter conforms to the local geometry we call it conformal alpha shape filtration. The local scale parameter is motivated from applications and previous algorithms in surface reconstruction. We show how conformal alpha shapes can be used for surface reconstruction of non-uniformly sampled surfaces, which is not possible with alpha shapes.

Note: Conference version has the title "Conformal Alpha Shapes".

  Persistence Barcodes for Shapes. with Gunnar Carlsson, Anne Collins, and Leonidas J. Guibas.
International Journal of Shape Modeling, 2005. (ps.gz) – doi:10.1142/S0218654305000761
Symposium on Geometry Processing, Nice, France, 2004. (ps.gz)

In this paper, we initiate a study of shape description and classification via the application of persistent homology to two tangential constructions on geometric objects. The homology of our first construction, the tangent complex, can distinguish between topologically identical shapes with different "sharp" features, such as corners. To capture "soft" curvature-dependent features, we define a second complex, the filtered tangent complex, obtained by parametrizing a family of increasing subcomplexes of the tangent complex. Applying persistent homology, we obtain a shape descriptor, called a barcode, that is a finite union of intervals. We define a metric over the space of such intervals, arriving at a continuous invariant that reflects the geometric properties of shapes.

  A Barcode Shape Descriptor for Curve Point Cloud Data. with Anne Collins, Gunnar Carlsson, and Leonidas J. Guibas.
Computers and Graphics, 2004 (Invited). (ps.gz) – doi:10.1016/j.cag.2004.08.015
Symposium on Point-Based Graphics, Zürich, Switzerland, 2004 (ps.gz)
Video (Quicktime)

In this paper, we present a complete computational pipeline for extracting a compact shape descriptor for curve point cloud data. Our shape descriptor, called a barcode, is based on a blend of techniques from differential geometry and algebraic topology. We also provide a metric over the space of barcodes, enabling fast comparison of PCDs for shape recognition and clustering. To demonstrate the feasibility of our approach, we have implemented our pipeline and provide experimental evidence in shape classification and parametrization.

  Computing Persistent Homology. with Gunnar Carlsson
Discrete and Computational Geometry, 2005 (ps.gz) (Errata) – doi:10.1007/s00454-004-1146-y
20th ACM Symposium on Computational Geometry, Brooklyn, NY, 2004 (ps.gz)

Application Video: Witness Complexes -- The Mumford Dataset (AVI)

We study the homology of a filtered d-dimensional simplicial complex K as a single algebraic entity and establish a correspondence that provides a simple description over fields. Our analysis enables us to derive a natural algorithm for computing persistent homology over an arbitrary field in any dimension. Our study also implies the lack of a simple classification over non-fields. Instead, we give an algorithm for computing individual persistent homology groups over an arbitrary PIDs in any dimension.

  Computing and Comprehending Topology: Persistence and Hierarchical Morse Complexes. Ph.D. Thesis. Urbana, Illinois, October 2001.
One-Sided (Hyperlinked)
Two-Sided (Hyperlinked)
Technical Report UIUCDCS-R-2001-2240

The fully hyperlinked versions include bookmarks, thumbnails, and backreferences, and are appropriate for online viewing. The two-sided versions have different odd and even margins for duplex printing and binding.

  Computing Linking Numbers of a Filtration. with Herbert Edelsbrunner
Homology, Homotopy, and Applications, 2003 (Invited).
1st Workshop on Algorithms in BioInformatics, Århus, Denmark, 2001

We develop fast algorithms for computing the linking number of a simplicial complex within a filtration. We give experimental results in applying our work toward the detection of non-trivial tangling in biomolecules, modeled as alpha complexes.

  Hierarchical Morse-Smale Complexes for Piecewise Linear 2-Manifolds. with Herbert Edelsbrunner and John Harer
French translation/interpretation by Sara Deriviere, 2006
Discrete and Computational Geometry, 2003 (Invited). – doi:10.1007/s00454-003-2926-5
17th ACM Symposium on Computational Geometry, Medford, MA, 2001

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.

Note: Conference version refers to "Morse complexes". We changed the title according to a reviewer's suggestion.

  Topological Persistence and Simplification. with Herbert Edelsbrunner and David Letscher
Discrete and Computational Geometry, 2002 (Invited). – doi:10.1007/s00454-002-2885-2
41st Symposium on Foundations of Computer Science, Redondo Beach, CA, 2000

We formalize a notion of topological simplification within the framework of a filtration, which is the history of a growing complex. We classify a topological change that happens during growth as either a feature or noise depending on its life-time or persistence within the filtration. We give fast algorithms for computing persistence and experimental evidence for their speed and utility.

  Fast Software for Box Intersection. with Herbert Edelsbrunner
International Journal of Computational Geometry and Applications, 2002 (Invited). – doi:10.1142/S0218195902000785
16th ACM Symposium on Computational Geometry, Hong Kong, 2000

We present fast implementations of a hybrid algorithm for reporting box and cube intersections. Our algorithm initially takes a divide-and-conquer approach and switches to simpler algorithms for low numbers of boxes. We use our implementations as engines to solve problems about geometric primitives. We look at two such problems in the category of quality analysis of surface triangulations.

  Context-Free Language Induction by Evolution of Deterministic Push-Down Automata Using Genetic Programming.
AAAI Fall Symposium. Boston, 1995.

The process of learning often consists of Inductive Inference, making generalizations from samples. The problem here is finding generalizations (Grammars) for Formal Languages from finite sets of positive and negative sample sentences. The focus of this paper is on Context-Free Languages (CFL's) as defined by Context-Free Grammars (CFG's), some of which are accepted by Deterministic Push-Down Automata (D-PDA). This paper describes a meta-language for constructing D-PDA's. This language is then combined with Genetic Programming to evolve D-PDA's which accept languages. The technique is illustrated with two favorite CFL's.