diff options
author | vrouvrea <vrouvrea@636b058d-ea47-450e-bf9e-a15bfbe3eedb> | 2018-04-04 06:11:17 +0000 |
---|---|---|
committer | vrouvrea <vrouvrea@636b058d-ea47-450e-bf9e-a15bfbe3eedb> | 2018-04-04 06:11:17 +0000 |
commit | 94c3a7705bf95983e76ff136108bf9846869868b (patch) | |
tree | addc5f9ae4d2fdf23c0ff2f0f161947e369f92c9 /src/Rips_complex/doc/Intro_rips_complex.h | |
parent | c06596e61c92f54a01756e1ba1babaff800f0f02 (diff) | |
parent | 1e55ed3f7ce467f598c66e18e6a7337476961588 (diff) |
Merge sparse rips branch in trunk
git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/trunk@3336 636b058d-ea47-450e-bf9e-a15bfbe3eedb
Former-commit-id: 01dcab006197637ccba9c29f8990375fe05ad7b4
Diffstat (limited to 'src/Rips_complex/doc/Intro_rips_complex.h')
-rw-r--r-- | src/Rips_complex/doc/Intro_rips_complex.h | 92 |
1 files changed, 76 insertions, 16 deletions
diff --git a/src/Rips_complex/doc/Intro_rips_complex.h b/src/Rips_complex/doc/Intro_rips_complex.h index 496c4218..5a551e60 100644 --- a/src/Rips_complex/doc/Intro_rips_complex.h +++ b/src/Rips_complex/doc/Intro_rips_complex.h @@ -29,28 +29,41 @@ namespace rips_complex { /** \defgroup rips_complex Rips complex * - * \author Clément Maria, Pawel Dlotko, Vincent Rouvreau + * \author Clément Maria, Pawel Dlotko, Vincent Rouvreau, Marc Glisse * * @{ * * \section ripsdefinition Rips complex definition * - * Rips_complex - * <a target="_blank" href="https://en.wikipedia.org/wiki/Vietoris%E2%80%93Rips_complex">(Wikipedia)</a> is a - * one skeleton graph that allows to construct a - * <a target="_blank" href="https://en.wikipedia.org/wiki/Simplicial_complex">simplicial complex</a> - * from it. - * The input can be a point cloud with a given distance function, or a distance matrix. - * - * The filtration value of each edge is computed from a user-given distance function, or directly from the distance - * matrix. + * The Vietoris-Rips complex + * <a target="_blank" href="https://en.wikipedia.org/wiki/Vietoris%E2%80%93Rips_complex">(Wikipedia)</a> + * is an abstract simplicial complex + * defined on a finite metric space, where each simplex corresponds to a subset + * of point whose diameter is smaller that some given threshold. + * Varying the threshold, we can also see the Rips complex as a filtration of + * the \f$(n-1)-\f$dimensional simplex, where the filtration value of each + * simplex is the diameter of the corresponding subset of points. + * + * This filtered complex is most often used as an approximation of the + * Čech complex. After rescaling (Rips using the length of the edges and Čech + * the half-length), they share the same 1-skeleton and are multiplicatively + * 2-interleaved or better. While it is slightly bigger, it is also much + * easier to compute. + * + * The number of simplices in the full Rips complex is exponential in the + * number of vertices, it is thus usually restricted, by excluding all the + * simplices with filtration value larger than some threshold, and keeping only + * the dim_max-skeleton. + * + * In order to build this complex, the algorithm first builds the graph. + * The filtration value of each edge is computed from a user-given distance + * function, or directly read from the distance matrix. + * In a second step, this graph is inserted in a simplicial complex, which then + * gets expanded to a flag complex. * - * All edges that have a filtration value strictly greater than a given threshold value are not inserted into - * the complex. + * The input can be given as a range of points and a distance function, or as a + * distance matrix. * - * When creating a simplicial complex from this one skeleton graph, Rips inserts the one skeleton graph into the data - * structure, and then expands the simplicial complex when required. - * * Vertex name correspond to the index of the point in the given range (aka. the point cloud). * * \image html "rips_complex_representation.png" "Rips-complex one skeleton graph representation" @@ -61,7 +74,36 @@ namespace rips_complex { * * If the Rips_complex interfaces are not detailed enough for your need, please refer to * <a href="_persistent_cohomology_2rips_persistence_step_by_step_8cpp-example.html"> - * rips_persistence_step_by_step.cpp</a> example, where the graph construction over the Simplex_tree is more detailed. + * rips_persistence_step_by_step.cpp</a> example, where the constructions of the graph and + * the Simplex_tree are more detailed. + * + * \section sparserips Sparse Rips complex + * + * Even truncated in filtration value and dimension, the Rips complex remains + * quite large. However, it is possible to approximate it by a much smaller + * filtered simplicial complex (linear size, with constants that depend on + * ε and the doubling dimension of the space) that is + * \f$(1+O(\epsilon))-\f$interleaved with it (in particular, their persistence + * diagrams are at log-bottleneck distance at most \f$O(\epsilon)\f$). + * + * The sparse Rips filtration was introduced by Don Sheehy + * \cite sheehy13linear. We are using the version described in + * \cite buchet16efficient (except that we multiply all filtration values + * by 2, to match the usual Rips complex), which proves a + * \f$\frac{1+\epsilon}{1-\epsilon}\f$-interleaving, although in practice the + * error is usually smaller. + * A more intuitive presentation of the idea is available in + * \cite cavanna15geometric, and in a video \cite cavanna15visualizing. + * + * The interface of `Sparse_rips_complex` is similar to the one for the usual + * `Rips_complex`, except that one has to specify the approximation factor, and + * there is no option to limit the maximum filtration value (the way the + * approximation is done means that larger filtration values are much cheaper + * to handle than low filtration values, so the gain would be too small). + * + * Theoretical guarantees are only available for \f$\epsilon<1\f$. The + * construction accepts larger values of ε, and the size of the complex + * keeps decreasing, but there is no guarantee on the quality of the result. * * \section ripspointsdistance Point cloud and distance function * @@ -104,6 +146,24 @@ namespace rips_complex { * * \include Rips_complex/full_skeleton_rips_for_doc.txt * + * + * \subsection sparseripspointscloudexample Example of a sparse Rips from a point cloud + * + * This example builds the full sparse Rips of a set of 2D Euclidean points, then prints some minimal + * information about the complex. + * + * \include Rips_complex/example_sparse_rips.cpp + * + * When launching: + * + * \code $> ./Rips_complex_example_sparse + * \endcode + * + * the program output may be (the exact output varies from one run to the next): + * + * \code Sparse Rips complex is of dimension 2 - 19 simplices - 7 vertices. + * \endcode + * * * * \section ripsdistancematrix Distance matrix |