From 1c28771ee5fd6acbbc3110adef8ae3c7b52d95e4 Mon Sep 17 00:00:00 2001 From: glisse Date: Mon, 22 Jan 2018 11:24:44 +0000 Subject: Some general doc. git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/sparserips-glisse@3146 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 8105c997b5541d0f3c8640e985de5d6810ab6be9 --- src/Rips_complex/doc/Intro_rips_complex.h | 66 +++++++++++++++++++++++-------- 1 file changed, 50 insertions(+), 16 deletions(-) (limited to 'src/Rips_complex') diff --git a/src/Rips_complex/doc/Intro_rips_complex.h b/src/Rips_complex/doc/Intro_rips_complex.h index 124dfec9..54afad66 100644 --- a/src/Rips_complex/doc/Intro_rips_complex.h +++ b/src/Rips_complex/doc/Intro_rips_complex.h @@ -29,28 +29,38 @@ 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 - * (Wikipedia) is a - * one skeleton graph that allows to construct a - * simplicial complex - * 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 + * (Wikipedia) 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 (they share the same 1-skeleton and are multiplicatively + * 2-interleaved or better), which is slightly bigger but 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 +71,31 @@ namespace rips_complex { * * If the Rips_complex interfaces are not detailed enough for your need, please refer to * - * rips_persistence_step_by_step.cpp example, where the graph construction over the Simplex_tree is more detailed. + * rips_persistence_step_by_step.cpp 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 ε). + * + * The sparse Rips filtration was introduced by Don Sheehy \cite + * sheehy13linear. We are using the version from \cite buchet16efficient. + * 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 * -- cgit v1.2.3