JavaScript isn't enabled in your browser, so this file can't be opened. Enable and reload.

1 of 42

DSC 291�Algorithmic foundation for �Topological Data Analysis�

Topic 2: Simplicial Complexes

a.k.a. how do we model space of interests?

Instructor: Yusu Wang

2 of 42

Overview

Simplicial complex

a specific type of topological space commonly used in practice to model data

Notations

Commonly used simplicial complexes from point cloud data (PCD)

3 of 42

Introduction to �Simplicial Complex

4 of 42

5 of 42

A (Geometric) Simplex

0-simplex

1-simplex

3-simplex

2-simplex

6 of 42

A (Geometric) Simplex

3-simplex

7 of 42

Simplicial complex

8 of 42

Simplicial complex

9 of 42

Abstract simplicial complex

10 of 42

Geometric realization

11 of 42

Star and links

12 of 42

Simplicial map

13 of 42

Simplicial map

14 of 42

A topological invariant – Euler Characteristics

15 of 42

Triangulation of a manifold

16 of 42

Triangulation of a manifold

17 of 42

�Common Complexes

18 of 42

19 of 42

Delaunay Complex

20 of 42

Delaunay Complex

21 of 42

Čech Complex

22 of 42

Nerves

23 of 42

Nerve Lemma

24 of 42

Nerve Lemma

25 of 42

26 of 42

Rips Complex

27 of 42

Rips and Čech Complexes

28 of 42

Witness complex

29 of 42

Witness Complexes

30 of 42

Intuition

31 of 42

Witness Complexes

32 of 42

Subsampling

33 of 42

Subsampling -cont

34 of 42

Subsampling -cont

35 of 42

Subsampling - cont

36 of 42

Graph Induced Complex

37 of 42

Graph Induced Complex

38 of 42

An example pipeline for high-D PCDs

39 of 42

Comparisons

40 of 42

Graph Induced Complex

GIC can also be used as a way to sparsify graphs while maintaining global structure.

41 of 42

Graph Induced Complex

42 of 42

FIN