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

1 files changed, 50 insertions, 16 deletions

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
- * <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 (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
  * <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
+ * &epsilon; 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 &epsilon;).
+ *
+ * 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 &epsilon;, 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
  *