Visual data mining based on differential topology: a survey <s> Figure 1 <s> I: Preliminaries on Manifolds.- 1. Manifolds.- 2. Differentiable Mappings and Submanifolds.- 3. Tangent Spaces.- 4. Partitions of Unity.- 5. Vector Bundles.- 6. Integration of Vector Fields.- II: Transversality.- 1. Sard's Theorem.- 2. Jet Bundles.- 3. The Whitney C? Topology.- 4. Transversality.- 5. The Whitney Embedding Theorem.- 6. Morse Theory.- 7. The Tubular Neighborhood Theorem.- III: Stable Mappings.- 1. Stable and Infinitesimally Stable Mappings.- 2. Examples.- 3. Immersions with Normal Crossings.- 4. Submersions with Folds.- IV: The Malgrange Preparation Theorem.- 1. The Weierstrass Preparation Theorem.- 2. The Malgrange Preparation Theorem.- 3. The Generalized Malgrange Preparation Theorem.- V: Various Equivalent Notions of Stability.- 1. Another Formulation of Infinitesimal Stability.- 2. Stability Under Deformations.- 3. A Characterization of Trivial Deformations.- 4. Infinitesimal Stability => Stability.- 5. Local Transverse Stability.- 6. Transverse Stability.- 7. Summary.- VI: Classification of Singularities, Part I: The Thom-Boardman Invariants.- 1. The Sr Classification.- 2. The Whitney Theory for Generic Mappings between 2-Manifolds.- 3. The Intrinsic Derivative.- 4. The Sr,s Singularities.- 5. The Thom-Boardman Stratification.- 6. Stable Maps Are Not Dense.- VII: Classification of Singularities, Part II: The Local Ring of a Singularity.- 1. Introduction.- 2. Finite Mappings.- 3. Contact Classes and Morin Singularities.- 4. Canonical Forms for Morin Singularities.- 5. Umbilics.- 6. Stable Mappings in Low Dimensions.- A. Lie Groups.- Symbol Index. <s> BIB001 </s> Visual data mining based on differential topology: a survey <s> Figure 1 <s> Researchers in the fields of computer graphics and geographical information systems GISs have extensively studied the methods of extracting terrain features such as peaks, pits, passes, ridges, and ravines from discrete elevation data. The existing techniques, however, do not guarantee the topological integrity of the extracted features because of their heuristic operations, which results in spurious features. Furthermore, there have been no algorithms for constructing topological graphs such as the surface network and the Reeb graph from the extracted peaks, pits, and passes. This paper presents new algorithms for extracting features and constructing the topological graphs using the features. Our algorithms enable us to extract correct terrain features; i.e., our method extracts the critical points that satisfy the Euler formula, which represents the topological invariant of smooth surfaces. This paper also provides an algorithm that converts the surface network to the Reeb graph for representing contour changes with respect to the height. The discrete elevation data used in this paper is a set of sample points on a terrain surface. Examples are presented to show that the algorithms also appeal to our visual cognition. <s> BIB002 </s> Visual data mining based on differential topology: a survey <s> Figure 1 <s> The authors introduce the contour spectrum, a user interface component that improves qualitative user interaction and provides real-time exact quantification in the visualization of isocontours. The contour spectrum is a signature consisting of a variety of scalar data and contour attributes, computed over the range of scalar values /spl omega//spl isin/R. They explore the use of surface, area, volume, and gradient integral of the contour that are shown to be univariate B-spline functions of the scalar value /spl omega/ for multi-dimensional unstructured triangular grids. These quantitative properties are calculated in real-time and presented to the user as a collection of signature graphs (plots of functions of /spl omega/) to assist in selecting relevant isovalues /spl omega//sub 0/ for informative visualization. For time-varying data, these quantitative properties can also be computed over time, and displayed using a 2D interface, giving the user an overview of the time-varying function, and allowing interaction in both isovalue and time step. The effectiveness of the current system and potential extensions are discussed. <s> BIB003 </s> Visual data mining based on differential topology: a survey <s> Figure 1 <s> We show that contour trees can be computed in all dimensions by a simple algorithm that merges two trees. Our algorithm extends, simplifies, and improves work of Tarasov and Vyalyi and of van Kreveld et al. <s> BIB004 </s> Visual data mining based on differential topology: a survey <s> Figure 1 <s> This paper introduces two efficient algorithms that compute the Contour Tree of a 3D scalar field F and its augmented version with the Betti numbers of each isosurface. The Contour Tree is a fundamental data structure in scientific visualization that is used to preprocess the domain mesh to allow optimal computation of isosurfaces with minimal overhead storage. The Contour Tree can also be used to build user interfaces reporting the complete topological characterization of a scalar field, as shown in Figure 1.The first part of the paper presents a new scheme that augments the Contour Tree with the Betti numbers of each isocontour in linear time. We show how to extend the scheme introduced in [3] with the Betti number computation without increasing its complexity. Thus, we improve on the time complexity from our previous approach [10] from O(m log m) to O(n log n + m), where m is the number of tetrahedra and n is the number of vertices in the domain of F.The second part of the paper introduces a new divide-and-conquer algorithm that computes the Augmented Contour Tree with improved efficiency. The central part of the scheme computes the output Contour Tree by merging two intermediate Contour Trees and is independent of the interpolant. In this way we confine any knowledge regarding a specific interpolant to an oracle that computes the tree for a single cell. We have implemented this oracle for the trilinear interpolant and plan to replace it with higher order interpolants when needed. The complexity of the scheme is O(n + t log n), where t is the number of critical points of F. For the first time we can compute the Contour Tree in linear time in many practical cases when t = O(n1 - e).Lastly, we report the running times for a parallel implementation of our algorithm, showing good scalability with the number of processors. <s> BIB005 </s> Visual data mining based on differential topology: a survey <s> Figure 1 <s> Topological volume skeletonization is a novel approach for automating transfer function design in visualization by extracting the topological structure of a volume dataset. The skeletonization process yields a graph called a volume skeleton tree, which consists of volumetric critical points and their connectivity. The resultant graph provides critical field values whose color and opacity are accentuated in the design of transfer functions for direct volume rendering. Visually pleasing results of volume visualization demonstrate the feasibility of the present approach. <s> BIB006 </s> Visual data mining based on differential topology: a survey <s> Figure 1 <s> The contour tree, an abstraction of a scalar field that encodes the nesting relationships of isosurfaces, can be used to accelerate isosurface extraction, to identify important isovalues for volume-rendering transfer functions, and to guide exploratory visualization through a flexible isosurface interface. Many real-world data sets produce unmanageably large contour trees which require meaningful simplification. We define local geometric measures for individual contours, such as surface area and contained volume, and provide an algorithm to compute these measures in a contour tree. We then use these geometric measures to simplify the contour trees, suppressing minor topological features of the data. We combine this with a flexible isosurface interface to allow users to explore individual contours of a dataset interactively. <s> BIB007 </s> Visual data mining based on differential topology: a survey <s> Figure 1 <s> Topological volume skeletons represent level-set graphs of 3D scalar fields, and have recently become crucial to visualizing the global isosurface transitions in the volume. However, it is still a time-consuming task to extract them, especially when input volumes are large-scale data and/or prone to small-amplitude noise. The paper presents an efficient method for accelerating the computation of such skeletons using adaptive tetrahedralization. The tetrahedralization is a top-down approach to linear interpolation of the scalar fields in that it selects tetrahedra to be subdivided adaptively using several criteria. As the criteria, the method employs a topological criterion as well as a geometric one in order to pursue all the topological isosurface transitions that may contribute to the global skeleton of the volume. The tetrahedralization also allows us to avoid unnecessary tracking of minor degenerate features that hide the global skeleton. Experimental results are included to demonstrate that the present method smoothes out the original scalar fields effectively without missing any significant topological features. <s> BIB008 </s> Visual data mining based on differential topology: a survey <s> Figure 1 <s> Recent development in the design of multi-dimensional transfer functions allows us to automatically generate comprehensible visualization images of given volumes by taking into account local features such as differentials and curvatures. However, especially when visualizing volumes obtained by scientific simulations, observers usually exploit their knowledge about the simulation settings as the clues to the effective control of visualization parameters for their own specific purposes. This paper therefore presents an objective-based framework for visualizing simulated volume datasets by introducing a new set of topological attributes. These topological attributes are calculated from the level-set graph of a given volume dataset, and thus differ from the conventional local attributes in that they also illuminate the global structure of the volume. The present framework provides a systematic means of emphasizing the underlying volume features, such as nested structures of isosurfaces, configuration of isosurface trajectories, and transitions of isosurface's topological type. Several combinations of the topological attributes together with the associated transfer function designs are devised and applied to real simulated datasets in order to demonstrate the feasibility of the present framework. <s> BIB009
Analyzing a discrete elevation model. Features of differential topology are extracted by tracking the topological change in cross-sectional contours with respect to the height. The boundary of the yellow region represents one of the cross sections of the terrain surface at height 160: the region itself corresponds to height ≥ 160 and corresponds to the subgraph in the join tree marked yellow in Figure 3 . shown in Figure 2 . Furthermore, we can also track the connectivity among the singular points to precisely locate the splitting and merging in the contour. In practice, the topological change in the inverse image of some scalar value is often described as a tree structure called a contour tree BIB003 as shown in Figure 3 , which has successfully been applied to various situations such as analyzing contour topology of terrain surfaces BIB002 , designing visualization parameters for volume rendering BIB006 , and extracting spatial embeddings of contours in volumes BIB009 . Constructing algorithms for computing such contour trees of scalar functions R n → R started from the mid 1990s, and early in 2000s Carr et al. BIB004 presented an excellent algorithm for constructing contour trees, which is fully sophisticated both in simplicity and in computational complexity and thus has been commonly employed so far. Although this algorithm intrinsically has no limitation on the dimension n of the data domain, it still suffers from practical implementation issues when n is equal to 4 or more due to the troubles in composing connectivity among discrete samples. This technical problem was alleviated by algorithms that were developed in the late 2000s, which aggressively incorporated dimensionality reduction approaches from the field of machine learning. These new algorithms successfully eliminate the limit on the number of data dimensions, and thus enabled computation of contour trees even from time-varying and higher-dimensional data samples. On the other hand, the dimension of the data range has long been limited to 1, since it is considerably difficult to track the change in the inverse image in terms of multiple function values simultaneously. Of course, we can construct a contour tree for each of the multiple function values individually while this scheme does not provide any information about relationships among the multiple function values. For example, it is preferable to extract some coherent relationships between temperature and pressure in some space when we try to extract features of differential topology from data samples of a multivariate function R 3 → R 2 in this case. In this article, we also show that recent technical challenges can solve this problem by extracting the topological change in a fiber, which is defined to be the intersection among the inverse images of the given multiple function values. These three types of approaches will be described in the following sections. 3 Analyzing samples of a function R 2 → R or R 3 → R As an example of the first type of data, we consider discrete samples of a scalar function f : R 2 → R, which represents a height field of a terrain surface as shown in Figure 1 . In the following, we assume that f is differentiable of class C ∞ . A point p ∈ R 2 is called a singular point We also define the number of negative eigenvalues of the Hessian matrix at p, i.e., to be the index of the singular point p. In the following, we assume that the singular points are all non-degenerate, i.e., the Hessian matrix is always non-degenerate. A scalar function whose singular points are all non-degenerate is called a Morse function, and it is known that the space of Morse functions is dense in the space of all functions: any given function can be approximated arbitrarily well by a Morse function (for example, see BIB001 ). In the case of such a height field, the singular points are classified into three categories as shown in Figure 2 . Note that in each category in Figure 2 the left hand side illustration depicts a terrain shape around each type of a singular point while the right hand side illustration shows the topological transition of the corresponding contour with respect to the height. As the reader can observe, a singular point corresponds to a point where a topological change arises in the corresponding contour. Now we move on to the case of one dimension higher, i.e., a set of discrete samples of a 3D scalar field f : R 3 → R. This case covers 3D volume data such as 3D medical images provided by measurement equipments (i.e. CT, MRI, etc.) and 3D spatial data obtained through computer simulations. In this case, a contour corresponds to an isosurface on which the scalar field values are all equal, and the singular points are classified into four different groups according to their indices, as long as the singular points are all non-degenerate. As described earlier, the primary advantage of data analysis based on differential topology is the capability to extract not only local features such as singular points but also the global structure of the entire data as the mutual connection among the local features, which easily allows us to represent the data in a hierarchical fashion. In particular, a tree structure called contour tree BIB003 serves as an effective tool for encoding topological changes in the inverse image according to the scalar function value changes, and thus has been employed in many visualization problems. For a given function f : R n → R, by contracting each connected component of the inverse images to a point, we get a space R f , which inherits the quotient topology from R n . It is known that R f has the structure of a graph in general and is often called the Reeb graph  of f . In some contexts, it is a tree and is called a contour tree. The standard version of an algorithm for constructing contour trees has been invented by Carr et al. BIB004 , and consists of the following steps ( Figure 3 ): 1. Constructing a join tree and a split tree, 2. Constructing an augmented contour tree, 3. Composing a final contour tree. The first step is to construct a join tree, which describes how connected components in the inverse image joins as the function value decreases. In the case of discrete http://www.pacific-mathforindustry.com/content/6/1/4 elevation samples shown in Figure 1 , we first triangulate the sample points to interpolate the height field over the 2D data domain first, and then compose a tree by incorporating the discrete samples in the order of the corresponding function values. Suppose that we construct the contour tree of the sample points contained in the yellow region as shown in Figure 1 . We first pick up the highest sample point at the height of 220 and add the corresponding vertex to the join tree. We then insert the second highest sample point at the height of 205 as a vertex that is connected with the previously inserted vertex, since it is also adjacent to that vertex in the triangulation of the terrain data. The next highest point at the height of 200 will be incorporated into the tree as a disjoint vertex, since it has no direct connection with the already registered vertices. Finally, when we insert the point at the height of 160, two disjoint sets of vertices will be merged into one. Figure 3 (a) shows a join tree of the entire set of discrete terrain data. A split tree can be constructed in the same way if we reorder the discrete samples in an ascending order with respect to the function value, as shown in Figure 3(b) . As demonstrated in Figure 3 (c) , a preliminary version of a contour tree called an augmented contour tree can be constructed, by identifying the topological branches in the inverse image by tracking the join tree from the top and the split tree from the bottom. Figure 3(d) presents the final version of the contour tree, which has been obtained by removing non-branching vertices from the augmented contour tree. As additional options, we can introduce steps for decomposing degenerate singular points into nondegenerate ones BIB002 BIB006 to better figure out the spatial configuration of the inverse image BIB009 , for simplifying the contour trees by pruning minor edges for noise removal BIB007 BIB008 , and for extracting change in genus of the inverse image especially for the case of 3D volumes BIB005 . In this way, especially for functions R 2 → R and R 3 → R, extracting features of differential topology can be accomplished by composing a proximity graph over the discrete samples first and then constructing a tree that represents the splitting and merging of the inverse images according to the function value changes. Figure 4 provides examples of contour trees extracted from 2D and 3D scalar fields using the algorithm described above.