@article{3332,
abstract = {Given an algebraic hypersurface O in ℝd, how many simplices are necessary for a simplicial complex isotopic to O? We address this problem and the variant where all vertices of the complex must lie on O. We give asymptotically tight worst-case bounds for algebraic plane curves. Our results gradually improve known bounds in higher dimensions; however, the question for tight bounds remains unsolved for d ≥ 3.},
author = {Kerber, Michael and Sagraloff, Michael},
journal = {Graphs and Combinatorics},
number = {3},
pages = {419 -- 430},
publisher = {Springer},
title = {{A note on the complexity of real algebraic hypersurfaces}},
doi = {10.1007/s00373-011-1020-7},
volume = {27},
year = {2011},
}
@article{3334,
author = {Edelsbrunner, Herbert and Pach, János and Ziegler, Günter},
journal = {Discrete & Computational Geometry},
number = {1},
pages = {1 -- 2},
publisher = {Springer},
title = {{Letter from the new editors-in-chief}},
doi = {10.1007/s00454-010-9313-9},
volume = {45},
year = {2011},
}
@inbook{3335,
abstract = {We study the topology of the Megaparsec Cosmic Web in terms of the scale-dependent Betti numbers, which formalize the topological information content of the cosmic mass distribution. While the Betti numbers do not fully quantify topology, they extend the information beyond conventional cosmological studies of topology in terms of genus and Euler characteristic. The richer information content of Betti numbers goes along the availability of fast algorithms to compute them. For continuous density fields, we determine the scale-dependence of Betti numbers by invoking the cosmologically familiar filtration of sublevel or superlevel sets defined by density thresholds. For the discrete galaxy distribution, however, the analysis is based on the alpha shapes of the particles. These simplicial complexes constitute an ordered sequence of nested subsets of the Delaunay tessellation, a filtration defined by the scale parameter, α. As they are homotopy equivalent to the sublevel sets of the distance field, they are an excellent tool for assessing the topological structure of a discrete point distribution. In order to develop an intuitive understanding for the behavior of Betti numbers as a function of α, and their relation to the morphological patterns in the Cosmic Web, we first study them within the context of simple heuristic Voronoi clustering models. These can be tuned to consist of specific morphological elements of the Cosmic Web, i.e. clusters, filaments, or sheets. To elucidate the relative prominence of the various Betti numbers in different stages of morphological evolution, we introduce the concept of alpha tracks. Subsequently, we address the topology of structures emerging in the standard LCDM scenario and in cosmological scenarios with alternative dark energy content. The evolution of the Betti numbers is shown to reflect the hierarchical evolution of the Cosmic Web. We also demonstrate that the scale-dependence of the Betti numbers yields a promising measure of cosmological parameters, with a potential to help in determining the nature of dark energy and to probe primordial non-Gaussianities. We also discuss the expected Betti numbers as a function of the density threshold for superlevel sets of a Gaussian random field. Finally, we introduce the concept of persistent homology. It measures scale levels of the mass distribution and allows us to separate small from large scale features. Within the context of the hierarchical cosmic structure formation, persistence provides a natural formalism for a multiscale topology study of the Cosmic Web.},
author = {Van De Weygaert, Rien and Vegter, Gert and Edelsbrunner, Herbert and Jones, Bernard and Pranav, Pratyush and Park, Changbom and Hellwing, Wojciech and Eldering, Bob and Kruithof, Nico and Bos, Patrick and Hidding, Johan and Feldbrugge, Job and Ten Have, Eline and Van Engelen, Matti and Caroli, Manuel and Teillaud, Monique},
booktitle = {Transactions on Computational Science XIV},
editor = {Gavrilova, Marina and Tan, Kenneth and Mostafavi, Mir},
pages = {60 -- 101},
publisher = {Springer},
title = {{Alpha, Betti and the Megaparsec Universe: On the topology of the Cosmic Web}},
doi = {10.1007/978-3-642-25249-5_3},
volume = {6970},
year = {2011},
}
@inproceedings{3336,
abstract = {We introduce TopoCut: a new way to integrate knowledge about topological properties (TPs) into random field image segmentation model. Instead of including TPs as additional constraints during minimization of the energy function, we devise an efficient algorithm for modifying the unary potentials such that the resulting segmentation is guaranteed with the desired properties. Our method is more flexible in the sense that it handles more topology constraints than previous methods, which were only able to enforce pairwise or global connectivity. In particular, our method is very fast, making it for the first time possible to enforce global topological properties in practical image segmentation tasks.},
author = {Chen, Chao and Freedman, Daniel and Lampert, Christoph},
booktitle = {CVPR: Computer Vision and Pattern Recognition},
location = {Colorado Springs, CO, USA},
pages = {2089 -- 2096},
publisher = {IEEE},
title = {{Enforcing topological constraints in random field image segmentation}},
doi = {10.1109/CVPR.2011.5995503},
year = {2011},
}
@inproceedings{3367,
abstract = {In this paper, we present the first output-sensitive algorithm to compute the persistence diagram of a filtered simplicial complex. For any Γ>0, it returns only those homology classes with persistence at least Γ. Instead of the classical reduction via column operations, our algorithm performs rank computations on submatrices of the boundary matrix. For an arbitrary constant δ ∈ (0,1), the running time is O(C(1-δ)ΓR(n)log n), where C(1-δ)Γ is the number of homology classes with persistence at least (1-δ)Γ, n is the total number of simplices, and R(n) is the complexity of computing the rank of an n x n matrix with O(n) nonzero entries. Depending on the choice of the rank algorithm, this yields a deterministic O(C(1-δ)Γn2.376) algorithm, a O(C(1-δ)Γn2.28) Las-Vegas algorithm, or a O(C(1-δ)Γn2+ε) Monte-Carlo algorithm for an arbitrary ε>0.},
author = {Chen, Chao and Kerber, Michael},
location = {Paris, France},
pages = {207 -- 216},
publisher = {ACM},
title = {{An output sensitive algorithm for persistent homology}},
doi = {10.1145/1998196.1998228},
year = {2011},
}
@article{3377,
abstract = {By definition, transverse intersections are stable under in- finitesimal perturbations. Using persistent homology, we ex- tend this notion to sizeable perturbations. Specifically, we assign to each homology class of the intersection its robust- ness, the magnitude of a perturbation necessary to kill it, and prove that robustness is stable. Among the applications of this result is a stable notion of robustness for fixed points of continuous mappings and a statement of stability for con- tours of smooth mappings.},
author = {Edelsbrunner, Herbert and Morozov, Dmitriy and Patel, Amit},
journal = {Foundations of Computational Mathematics},
number = {3},
pages = {345 -- 361},
publisher = {Springer},
title = {{Quantifying transversality by measuring the robustness of intersections}},
doi = {10.1007/s10208-011-9090-8},
volume = {11},
year = {2011},
}
@article{3378,
abstract = {The theory of intersection homology was developed to study the singularities of a topologically stratified space. This paper in- corporates this theory into the already developed framework of persistent homology. We demonstrate that persistent intersec- tion homology gives useful information about the relationship between an embedded stratified space and its singularities. We give, and prove the correctness of, an algorithm for the computa- tion of the persistent intersection homology groups of a filtered simplicial complex equipped with a stratification by subcom- plexes. We also derive, from Poincare ́ Duality, some structural results about persistent intersection homology.},
author = {Bendich, Paul and Harer, John},
journal = {Foundations of Computational Mathematics},
number = {3},
pages = {305 -- 336},
publisher = {Springer},
title = {{Persistent intersection homology}},
doi = {10.1007/s10208-010-9081-1},
volume = {11},
year = {2011},
}
@inproceedings{3782,
abstract = {In cortex surface segmentation, the extracted surface is required to have a particular topology, namely, a two-sphere. We present a new method for removing topology noise of a curve or surface within the level set framework, and thus produce a cortical surface with correct topology. We define a new energy term which quantifies topology noise. We then show how to minimize this term by computing its functional derivative with respect to the level set function. This method differs from existing methods in that it is inherently continuous and not digital; and in the way that our energy directly relates to the topology of the underlying curve or surface, versus existing knot-based measures which are related in a more indirect fashion. The proposed flow is validated empirically.},
author = {Chen, Chao and Freedman, Daniel},
booktitle = { Conference proceedings MCV 2010},
location = {Beijing, China},
pages = {31 -- 42},
publisher = {Springer},
title = {{Topology noise removal for curve and surface evolution}},
doi = {10.1007/978-3-642-18421-5_4},
volume = {6533},
year = {2010},
}
@inbook{3795,
abstract = {The (apparent) contour of a smooth mapping from a 2-manifold to the plane, f: M → R2 , is the set of critical values, that is, the image of the points at which the gradients of the two component functions are linearly dependent. Assuming M is compact and orientable and measuring difference with the erosion distance, we prove that the contour is stable.},
author = {Edelsbrunner, Herbert and Morozov, Dmitriy and Patel, Amit},
booktitle = {Topological Data Analysis and Visualization: Theory, Algorithms and Applications},
pages = {27 -- 42},
publisher = {Springer},
title = {{The stability of the apparent contour of an orientable 2-manifold}},
doi = {10.1007/978-3-642-15014-2_3},
year = {2010},
}
@inproceedings{3848,
abstract = {We define the robustness of a level set homology class of a function f:XR as the magnitude of a perturbation necessary to kill the class. Casting this notion into a group theoretic framework, we compute the robustness for each class, using a connection to extended persistent homology. The special case X=R3 has ramifications in medical imaging and scientific visualization.},
author = {Bendich, Paul and Edelsbrunner, Herbert and Morozov, Dmitriy and Patel, Amit},
location = {Liverpool, UK},
pages = {1 -- 10},
publisher = {Springer},
title = {{The robustness of level sets}},
doi = {10.1007/978-3-642-15775-2_1},
volume = {6346},
year = {2010},
}