2014 | Book

A Short Course in Computational Geometry and Topology

Author: Herbert Edelsbrunner

Publisher: Springer International Publishing

Book Series : SpringerBriefs in Applied Sciences and Technology

Part of: Springer Professional "Business + Economics & Engineering + Technology" , Springer Professional "Engineering + Technology" , Springer Professional "Business + Economics"

Table of Contents

About this book

This monograph presents a short course in computational geometry and topology. In the first part the book covers Voronoi diagrams and Delaunay triangulations, then it presents the theory of alpha complexes which play a crucial role in biology. The central part of the book is the homology theory and their computation, including the theory of persistence which is indispensable for applications, e.g. shape reconstruction. The target audience comprises researchers and practitioners in mathematics, biology, neuroscience and computer science, but the book may also be beneficial to graduate students of these fields.

Frontmatter

Chapter 1. Roots of Geometry and Topology

Abstract

Geometric questions have been pondered by people for thousands of years.

Herbert Edelsbrunner

Tessellations

Frontmatter

Chapter 2. Voronoi and Delaunay Diagrams

Abstract

The goal of this book is the introduction of the Voronoi diagram and the Delaunay triangulation of a finite set of points in the plane, and an elucidation of their dual relationship.

Herbert Edelsbrunner

Chapter 3. Weighted Diagrams

Abstract

Every region in a 2-dimensional Voronoi diagram consists of all points for which the corresponding site minimizes the Euclidean distance.

Herbert Edelsbrunner

Chapter 4. Three Dimensions

Abstract

Voronoi diagrams and Delaunay triangulations in \({{\mathbb R}}^3\) are more interesting and more difficult to understand than in \({{\mathbb R}}^2\). In this section, we develop some intuition by considering these tessellations for a few symmetric point sets.

Herbert Edelsbrunner

Backmatter

Complexes

Frontmatter

Chapter 5. Alpha Complexes

Abstract

The original motivation for the concept of alpha shapes was the desire to develop a concrete version of the intuitive notion of ‘shape’ of a finite point set. Starting from this idea, we explore connections to Voronoi diagrams and Delaunay triangulations.

Herbert Edelsbrunner

Chapter 6. Holes

Abstract

Being possibly non-convex, alpha shapes can have many interesting features, some of which that are best classified as types of holes. We begin with the easy 2-dimensional case, noting that the types and structure of holes gets progressively more complicated as the dimension increases.

Herbert Edelsbrunner

Chapter 7. Area Formulas

Abstract

Perhaps surprisingly, \(\alpha \)-complexes are useful in measuring a union of balls in two and higher dimensions.

Herbert Edelsbrunner

Backmatter

Homology

Frontmatter

Chapter 8. Topological Spaces

Abstract

In geometry, we can decide which points are near and which are far by computing distance. In topology, no such notion is available and distance is replaced by the weaker concept of neighborhoods.

Herbert Edelsbrunner

Chapter 9. Homology Groups

Abstract

Given a topological space, its homology is a formal, algebraic way to talk about its connectivity. Better known than the homology groups are their ranks,which are the Betti numbers of the space.

Herbert Edelsbrunner

Chapter 10. Complex Construction

Abstract

There are not many ways to automatically construct interesting topological spaces, and by ‘interesting’ we mean spaces that go beyond the designed ones, such as the ball, and the sphere.

Herbert Edelsbrunner

Backmatter

Persistence

Frontmatter

Chapter 11. Filtrations

Abstract

Complicated shapes and data sets—in particular those that occur in nature—have different appearance depending on the resolution of the observation.

Herbert Edelsbrunner

Chapter 12. PL Functions

Abstract

Other than from alpha, Čech, and Vietoris-Rips complexes, we get filtrations from real-valued functions on topological spaces.

Herbert Edelsbrunner

Chapter 13. Matrix Reduction

Abstract

We have seen how mathematical reasoning can be used to compute persistent homology for simple filtrations.

Herbert Edelsbrunner

Backmatter

Title: A Short Course in Computational Geometry and Topology
Author: Herbert Edelsbrunner
Publisher: Springer International Publishing
Electronic ISBN: 978-3-319-05957-0
Print ISBN: 978-3-319-05956-3
DOI: https://doi.org/10.1007/978-3-319-05957-0