Search

Homology has long been accepted as an important computational tool for quantifying complex structures. In many applications these structures arise as nodal domains of real-valued functions and are therefore amenable only to a numerical study based on suitable discretizations. Such an approach immediately raises the question of how accurately the resulting homology can be computed. In this paper we present an algorithm for correctly computing the homology of one- and two-dimensional nodal domains. The approach relies on constructing an appropriate cubical approximation for the nodal domain based on the behavior of the defining function at the vertices of a fixed grid. Betti numbers for these cubical sets are readily computable using [T. Kaczynski, K. Mischaikow, and M. Mrozek, Computational Homology, Springer-Verlag, New York, 2004; W. Kalies, M. Mrozek, and P. Pilarczyk, Computational Homology Project, http://chomp.rutgers.edu/ (2006)]. Here, we present a technique to verify that the cubical representation is homeomorphic to the nodal domain and therefore preserves homology. To illustrate this approach we consider examples from three classes of nodal domains, including the time-dependent patterns generated by the Cahn-Hilliard model for spinodal decomposition. We use these results to examine the probability of correct homology computations given specific grid sizes as related to the analytic estimates presented in [S. Day et al., Electron. Res. Announc. Amer. Math. Soc., 13 (2007), pp. 60-73; K. Mischaikow and T. Wanner, Ann. Appl. Probab., 17 (2007), pp. 980-1018; K. Mischaikow and T. Wanner, submitted; P. Niyogi, S. Smale, and S. Weinberger, Discrete Comput. Geom., 39 (2008), pp. 419-441]. [ABSTRACT FROM AUTHOR]

Simple point detection is an important task for several problems in discrete geometry, such as topology preserving thinning in image processing to compute discrete skeletons. In this paper, the approach to simple point detection is based on techniques from cubical homology, a framework ideally suited for problems in image processing. A (d-dimensional) unitary cube (for a d-dimensional digital image) is associated with every discrete picture element, instead of a point in ϵd (the d-dimensional Euclidean space) as has been done previously. A simple point in this setting then refers to the removal of a unitary cube without changing the topology of the cubical complex induced by the digital image. The main result is a characterization of a simple point p (i.e., simple unitary cube) in terms of the homology groups of the (3d - 1) neighborhood of p for arbitrary, finite dimensions [ABSTRACT FROM AUTHOR]