1 files changed, 90 insertions, 15 deletions
diff --git a/doc/Witness_complex/Witness_complex_doc.h b/doc/Witness_complex/Witness_complex_doc.h
index 60dfd27b..171a185f 100644
--- a/doc/Witness_complex/Witness_complex_doc.h
+++ b/doc/Witness_complex/Witness_complex_doc.h
@@ -8,31 +8,106 @@
 
    \image html "Witness_complex_representation.png" "Witness complex representation"
 
-   \section Definitions
+   \section witnessdefinitions Definitions
 
-   Witness complex \f$ Wit(W,L) \f$  is a simplicial complex defined on two sets of points in \f$\mathbb{R}^D\f$:
+   Witness complex is a simplicial complex defined on two sets of points in \f$\mathbb{R}^D\f$:
 
    \li \f$W\f$ set of **witnesses** and 
-   \li \f$L \subseteq W\f$ set of **landmarks**.
+   \li \f$L\f$ set of **landmarks**.
 
-   The simplices are based on landmarks
-   and a simplex belongs to the witness complex if and only if it is witnessed, that is:
+   Even though often the set of landmarks \f$L\f$ is a subset of the set of witnesses \f$ W\f$, it is not a requirement for the current implementation.
 
-   \f$ \sigma \subset L \f$ is witnessed if there exists a point \f$w \in W\f$ such that 
-   w is closer to the vertices of \f$ \sigma \f$ than other points in \f$ L \f$ and all of its faces are witnessed as well. 
- 
-   The data structure is described in \cite boissonnatmariasimplextreealgorithmica .
+   Landmarks are the vertices of the simplicial complex
+   and witnesses help to decide on which simplices are inserted via a predicate "is witnessed".
 
-   \section Implementation
+   De Silva and Carlsson in their paper \cite de2004topological differentiate **weak witnessing** and **strong witnessing**:
 
-   The principal class of this module is Gudhi::Witness_complex.
+   - *weak*:   \f$ \sigma \subset L \f$ is witnessed by \f$ w \in W\f$ if \f$ \forall l \in \sigma,\ \forall l' \in \mathbf{L \setminus \sigma},\ d(w,l) \leq d(w,l') \f$
+   - *strong*: \f$ \sigma \subset L \f$ is witnessed by \f$ w \in W\f$ if \f$ \forall l \in \sigma,\ \forall l' \in \mathbf{L},\ d(w,l) \leq d(w,l') \f$
 
-   In both cases, the constructor for this class takes a {witness}x{closest_landmarks} table, where each row represents a witness and consists of landmarks sorted by distance to this witness.
-   This table can be constructed by two additional classes Landmark_choice_by_furthest_point and Landmark_choice_by_random_point also included in the module.
+   where \f$ d(.,.) \f$ is a distance function.
 
-   *\image html "bench_Cy8.png" "Running time as function on number of landmarks" width=10cm
-   *\image html "bench_sphere.png" "Running time as function on number of witnesses for |L|=300" width=10cm
+   Both definitions can be relaxed by a real value \f$\alpha\f$:
+
+   - *weak*:   \f$ \sigma \subset L \f$ is \f$\alpha\f$-witnessed by \f$ w \in W\f$ if \f$ \forall l \in \sigma,\ \forall l' \in \mathbf{L \setminus \sigma},\ d(w,l)^2 \leq d(w,l')^2 + \alpha^2 \f$
+   - *strong*: \f$ \sigma \subset L \f$ is \f$\alpha\f$-witnessed by \f$ w \in W\f$ if \f$ \forall l \in \sigma,\ \forall l' \in \mathbf{L},\ d(w,l)^2 \leq d(w,l')^2 + \alpha^2 \f$
+
+   which leads to definitions of **weak relaxed witness complex** (or just relaxed witness complex for short) and **strong relaxed witness complex** respectively.
+
+   \image html "swit.svg" "Strongly witnessed simplex"
+
+   In particular case of 0-relaxation, weak complex corresponds to **witness complex** introduced in \cite de2004topological, whereas 0-relaxed strong witness complex consists of just vertices and is not very interesting.
+   Hence for small relaxation weak version is preferable.
+   However, to capture the homotopy type (for example using Gudhi::persistent_cohomology::Persistent_cohomology) it is often necessary to work with higher filtration values. In this case strong relaxed witness complex is faster to compute and offers similar results.
+
+   \section witnessimplementation Implementation
    
+   The two complexes described above are implemented in the corresponding classes 
+   - Gudhi::witness_complex::Witness_complex
+   - Gudhi::witness_complex::Euclidean_witness_complex
+   - Gudhi::witness_complex::Strong_witness_complex
+   - Gudhi::witness_complex::Euclidean_strong_witness_complex
+
+   The construction of the Euclidean versions of complexes follow the same scheme:
+   1. Construct a search tree on landmarks (for that Gudhi::spatial_searching::Kd_tree_search is used internally).
+   2. Construct lists of nearest landmarks for each witness (special structure Gudhi::witness_complex::Active_witness is used internally).
+   3. Construct the witness complex for nearest landmark lists.
+
+   In the non-Euclidean classes, the lists of nearest landmarks are supposed to be given as input.
+
+   The constructors take on the steps 1 and 2, while the function 'create_complex' executes the step 3.
+
+   \section witnessexample1 Example 1: Constructing weak relaxed witness complex from an off file
+
+   Let's start with a simple example, which reads an off point file and computes a weak witness complex.
+
+   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~{.cpp}
+   
+#include <gudhi/Simplex_tree.h>
+#include <gudhi/Euclidean_witness_complex.h>
+#include <gudhi/pick_n_random_points.h>
+#include <gudhi/Points_off_io.h>
+
+#include <CGAL/Epick_d.h>
+
+#include <string>
+#include <vector>
+
+typedef CGAL::Epick_d<CGAL::Dynamic_dimension_tag> K;
+typedef typename K::Point_d Point_d;
+typedef typename Gudhi::witness_complex::Euclidean_witness_complex<K> Witness_complex;
+typedef std::vector< Vertex_handle > typeVectorVertex;
+typedef std::vector< Point_d > Point_vector;
+
+int main(int argc, char * const argv[]) {
+  std::string file_name = argv[1];
+  int nbL = atoi(argv[2]), lim_dim = atoi(argv[4]);
+  double alpha2 = atof(argv[3]);
+  Gudhi::Simplex_tree<> simplex_tree;
+
+  // Read the point file
+  Point_vector point_vector, landmarks;
+  Gudhi::Points_off_reader<Point_d> off_reader(file_name);
+  point_vector = Point_vector(off_reader.get_point_cloud());
+
+  // Choose landmarks
+  Gudhi::subsampling::pick_n_random_points(point_vector, nbL, std::back_inserter(landmarks));
+
+  // Compute witness complex
+  Witness_complex witness_complex(landmarks,
+                                  point_vector);
+
+  witness_complex.create_complex(simplex_tree, alpha2, lim_dim);
+}
+
+   
+   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+   \section witnessexample2 Example2: Computing persistence using strong relaxed witness complex
+
+   Here is an example of constructing a strong witness complex filtration and computing persistence on it:
+
+   \include Witness_complex/example_strong_witness_persistence.cpp
 
    \copyright GNU General Public License v3.