ABSTRACT

According to the Oxford English Dictionary, the word topology is derived from topos (τo´πoς) meaning place, and -logy (λoγια), 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. The field of geometry studies intrinsic properties that are invariant under rigidmotion, such as the

curvature of a surface. In contrast, topology studies invariants under continuous deformations. The larger set of transformations enables topology to extract more qualitative information about a space, such as the number of connected components or tunnels. Computational topology has theoretical and practical goals. Theoretically, we look at the tractability and complexity of each problem, as well as the design of efficient data structures and algorithms. Practically, we are interested in heuristics and fast software for solving problems that arise in diverse disciplines. Our input is often a finite discrete set of noisy samples from some underlying space. This type of input has renewed interest

in combinatorial and algebraic topology, areas that had been overshadowed by point set topology in the last one hundred years. Computational topology developed in response to topological impediments emerging fromwithin

geometric problems. In computer graphics, researchers encountered the problem of connectivity in reconstructing watertight surfaces from point sets. Often, their heuristics resulted in surfaces with extraneous holes or tunnels that had to be detected and removed before proper geometric processing was feasible. Researchers in computational geometry provided guaranteed surface reconstruction algorithms that depended on sampling conditions on the input. These results required concepts from topology, provoking an interest in the subject. Topological problems also arise naturally in areas that do not deal directly with geometry. In robotics, researchers need to understand the connectivity of the configuration space of a robot for computing optimal trajectories that minimize resource consumption. In biology, the thermodynamics hypothesis states that proteins fold to their native states along such optimal trajectories. In sensor networks, determining coverage without localizing the sensors requires deriving global information from local connections. Once again the question of connectivity arises, steering us toward a topological understanding of the problem. Like topology, computational topology is a large and diverse area. The aim of this chapter is

not to be comprehensive, but to describe the fundamental concepts, methods, and structures that permeate the field. We begin with our objects of study, topological spaces and their combinatorial representations, in Section 3.2. We study these spaces through topological invariants, which we formalize in Section 3.3, classifying all surfaces, and introducing both combinatorial and algebraic invariants in the process. Sections 3.4 and 3.5 focus on homology and persistent homology, which are algebraic invariants that derive their popularity from their computability. Geometry and topology are intrinsically entangled, as revealed byMorse theory through additional structures in Section 3.6. For topological data analysis, we describe methods for deriving combinatorial structures that represent point sets in Section 3.7. We end the chapter with a brief discussion of geometric issues in Section 3.8.