Cubical complex

## Classes | |

class | Gudhi::cubical_complex::Bitmap_cubical_complex< T > |

Cubical complex represented as a bitmap. More... | |

class | Gudhi::cubical_complex::Bitmap_cubical_complex_base< T > |

Cubical complex represented as a bitmap, class with basic implementation. More... | |

class | Gudhi::cubical_complex::Bitmap_cubical_complex_periodic_boundary_conditions_base< T > |

Cubical complex with periodic boundary conditions represented as a bitmap. More... | |

Bitmap_cubical_complex is an example of a structured complex useful in computational mathematics (specially rigorous numerics) and image analysis. The presented implementation of cubical complexes is based on the following definition.

An *elementary interval* is an interval of a form , or , for . The first one is called *non-degenerate*, while the second one is *degenerate* interval. A *boundary of a elementary interval* is a chain in case of non-degenerated elementary interval and in case of degenerate elementary interval. An *elementary cube* is a product of elementary intervals, . *Embedding dimension* of a cube is n, the number of elementary intervals (degenerate or not) in the product. A *dimension of a cube* is the number of non degenerate elementary intervals in the product. A *boundary of a cube* is a chain obtained in the following way:

A *cubical complex* is a collection of cubes closed under operation of taking boundary (i.e. boundary of every cube from the collection is in the collection). A cube in cubical complex is *maximal* if it is not in a boundary of any other cube in . A *support* of a cube is the set in occupied by ( is the embedding dimension of ).

Cubes may be equipped with a filtration values in which case we have filtered cubical complex. All the cubical complexes considered in this implementation are filtered cubical complexes (although, the range of a filtration may be a set of two elements).

For further details and theory of cubical complexes, please consult [14] as well as the following paper [20] .

The implementation of Cubical complex provides a representation of complexes that occupy a rectangular region in . This extra assumption allows for a memory efficient way of storing cubical complexes in a form of so called bitmaps. Let , for , be the considered rectangular region and let be a filtered cubical complex having the rectangle as its support. Note that the structure of the coordinate system gives a way a lexicographical ordering of cells of . This ordering is a base of the presented bitmap-based implementation. In this implementation, the whole cubical complex is stored as a vector of the values of filtration. This, together with dimension of and the sizes of in all directions, allows to determine, dimension, neighborhood, boundary and coboundary of every cube .

Note that the cubical complex in the figure above is, in a natural way, a product of one dimensional cubical complexes in . The number of all cubes in each direction is equal , where is the number of maximal cubes in the considered direction. Let us consider a cube at the position in the bitmap. Knowing the sizes of the bitmap, by a series of modulo operation, we can determine which elementary intervals are present in the product that gives the cube . In a similar way, we can compute boundary and the coboundary of each cube. Further details can be found in the literature.

In the current implantation, filtration is given at the maximal cubes, and it is then extended by the lower star filtration to all cubes. There are a number of constructors that can be used to construct cubical complex by users who want to use the code directly. They can be found in the *Bitmap_cubical_complex* class. Currently one input from a text file is used. It uses a format used already in Perseus software (http://www.sas.upenn.edu/~vnanda/perseus/) by Vidit Nanda. Below we are providing a description of the format. The first line contains a number d begin the dimension of the bitmap (2 in the example below). Next d lines are the numbers of top dimensional cubes in each dimensions (3 and 3 in the example below). Next, in lexicographical order, the filtration of top dimensional cubes is given (1 4 6 8 20 4 7 6 5 in the example below).

The input file for the following complex is:

2 3 3 1 4 6 8 20 4 7 6 5

Often one would like to impose periodic boundary conditions to the cubical complex. Let be a box that is decomposed with a cubical complex . Imposing periodic boundary conditions in the direction i, means that the left and the right side of a complex are considered the same. In particular, if for a bitmap periodic boundary conditions are imposed in all directions, then complex became n-dimensional torus. One can use various constructors from the file Bitmap_cubical_complex_periodic_boundary_conditions_base.h to construct cubical complex with periodic boundary conditions. One can also use Perseus style input files. To indicate periodic boundary conditions in a given direction, then number of top dimensional cells in this direction have to be multiplied by -1. For instance:

2 -3 3 1 4 6 8 20 4 7 6 5

Indicate that we have imposed periodic boundary conditions in the direction x, but not in the direction y.

End user programs are available in example/Bitmap_cubical_complex folder.

- Copyright
- GNU General Public License v3.

GUDHI Version 2.0.0 - C++ library for Topological Data Analysis (TDA) and Higher Dimensional Geometry Understanding. | Generated on Wed Apr 19 2017 22:26:16 for GUDHI by 1.8.11 |