Čech complex

## Classes | |

class | Gudhi::cech_complex::Cech_complex< SimplicialComplexForProximityGraph, ForwardPointRange > |

Cech complex data structure. More... | |

Čech complex (Wikipedia) is a simplicial complex constructed from a proximity graph. The set of all simplices is filtered by the radius of their minimal enclosing ball.

The input shall be a point cloud in an Euclidean space.

- Remarks
- For people only interested in the topology of the Čech complex (for instance persistence), Alpha complex is equivalent to the Čech complex and much smaller if you do not bound the radii. Čech complex can still make sense in higher dimension precisely because you can bound the radii.

Cech_complex first builds a proximity graph from a point cloud. The filtration value of each edge of the `Gudhi::Proximity_graph`

is computed from `Gudhi::Minimal_enclosing_ball_radius`

function.

All edges that have a filtration value strictly greater than a user given maximal radius value, \(max\_radius\), are not inserted into the complex.

Vertex name correspond to the index of the point in the given range (aka. the point cloud).

When creating a simplicial complex from this proximity graph, Cech_complex inserts the proximity graph into the simplicial complex data structure, and then expands the simplicial complex when required.

On this example, as edges \((x,y)\), \((y,z)\) and \((z,y)\) are in the complex, the minimal ball radius containing the points \((x,y,z)\) is computed.

\((x,y,z)\) is inserted to the simplicial complex with the filtration value set with \(mini\_ball\_radius(x,y,z))\) iff \(mini\_ball\_radius(x,y,z)) \leq max\_radius\).

And so on for higher dimensions.

The minimal ball radius computation is insured by the miniball software (V3.0) - Smallest Enclosing Balls of Points - and distributed with GUDHI. Please refer to the miniball software design description for more information about this computation.

This radius computation is the reason why the Cech_complex is taking much more time to be computed than the Rips complex but it offers more topological guarantees.

If the Cech_complex interfaces are not detailed enough for your need, please refer to cech_complex_step_by_step.cpp example, where the graph construction over the Simplex_tree is more detailed.

This example builds the proximity graph from the given points, and maximal radius values. Then it creates a `Simplex_tree`

with it.

Then, it is asked to display information about the simplicial complex.

#include <gudhi/Cech_complex.h>

#include <gudhi/Simplex_tree.h>

#include <iostream>

#include <string>

#include <vector>

#include <array>

int main() {

// Type definitions

using Point_cloud = std::vector<std::array<double, 2>>;

Point_cloud points;

points.push_back({1., 0.}); // 0

points.push_back({0., 1.}); // 1

points.push_back({2., 1.}); // 2

points.push_back({3., 2.}); // 3

points.push_back({0., 3.}); // 4

points.push_back({3. + std::sqrt(3.), 3.}); // 5

points.push_back({1., 4.}); // 6

points.push_back({3., 4.}); // 7

points.push_back({2., 4. + std::sqrt(3.)}); // 8

points.push_back({0., 4.}); // 9

points.push_back({-0.5, 2.}); // 10

// ----------------------------------------------------------------------------

// Init of a Cech complex from points

// ----------------------------------------------------------------------------

Filtration_value max_radius = 1.;

Cech_complex cech_complex_from_points(points, max_radius);

Simplex_tree stree;

cech_complex_from_points.create_complex(stree, 2);

// ----------------------------------------------------------------------------

// Display information about the one skeleton Cech complex

// ----------------------------------------------------------------------------

std::cout << "Cech complex is of dimension " << stree.dimension() << " - " << stree.num_simplices() << " simplices - "

<< stree.num_vertices() << " vertices." << std::endl;

std::cout << "Iterator on Cech complex simplices in the filtration order, with [filtration value]:" << std::endl;

std::cout << " ( ";

std::cout << vertex << " ";

}

std::cout << ") -> "

std::cout << std::endl;

}

return 0;

}

When launching (maximal enclosing ball radius is 1., is expanded until dimension 2):

$> ./Cech_complex_example_from_points

the program output is:

Iterator on Cech complex simplices in the filtration order, with [filtration value]:

( 0 ) -> [0]

( 1 ) -> [0]

( 2 ) -> [0]

( 3 ) -> [0]

( 4 ) -> [0]

( 5 ) -> [0]

( 6 ) -> [0]

( 7 ) -> [0]

( 8 ) -> [0]

( 9 ) -> [0]

( 10 ) -> [0]

( 9 4 ) -> [0.5]

( 9 6 ) -> [0.5]

( 10 1 ) -> [0.559017]

( 10 4 ) -> [0.559017]

( 1 0 ) -> [0.707107]

( 2 0 ) -> [0.707107]

( 3 2 ) -> [0.707107]

( 6 4 ) -> [0.707107]

( 9 6 4 ) -> [0.707107]

( 2 1 ) -> [1]

( 2 1 0 ) -> [1]

( 4 1 ) -> [1]

( 5 3 ) -> [1]

( 7 3 ) -> [1]

( 7 5 ) -> [1]

( 7 6 ) -> [1]

( 8 6 ) -> [1]

( 8 7 ) -> [1]

( 10 4 1 ) -> [1]

GUDHI Version 2.3.0 - C++ library for Topological Data Analysis (TDA) and Higher Dimensional Geometry Understanding. - Copyright : GPL v3 | Generated on Tue Sep 4 2018 14:33:00 for GUDHI by Doxygen 1.8.13 |