From 309d5aa575735acefabc33abade72637c52fb931 Mon Sep 17 00:00:00 2001 From: skachano Date: Fri, 7 Oct 2016 16:08:41 +0000 Subject: Added a big chunk of documentation. +small fixes git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/relaxed-witness@1679 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: d3166034bf662121bc21583bb027c67f736e904c --- src/Witness_complex/doc/Witness_complex_doc.h | 46 ++++++++++++++++++++------- 1 file changed, 34 insertions(+), 12 deletions(-) (limited to 'src/Witness_complex/doc') diff --git a/src/Witness_complex/doc/Witness_complex_doc.h b/src/Witness_complex/doc/Witness_complex_doc.h index 60dfd27b..1d6e9da2 100644 --- a/src/Witness_complex/doc/Witness_complex_doc.h +++ b/src/Witness_complex/doc/Witness_complex_doc.h @@ -6,33 +6,55 @@ \author Siargey Kachanovich - \image html "Witness_complex_representation.png" "Witness complex representation" + \image html "Witness_complex_representation.png" "Witness complex representation in a Simplex tree (from \cite boissonnatmariasimplextreealgorithmica)" \section 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**. + + 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. The simplices are based on landmarks - and a simplex belongs to the witness complex if and only if it is witnessed, that is: + and witnesses help to decide on which simplices are inserted via a predicate "is witnessed". + + De Silva and Carlsson in their paper \cite de2004topological differentiate **weak witnessing** and **strong witnessing**: + + - *weak*: \f$ \sigma \subset L \f$ is witnessed by \f$ w \in W\f$ if \f$ \forall l \in \sigma,\ \forall l' \in 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 L,\ d(w,l) \leq d(w,l') \f$ + + where \f$ d(.,.) \f$ is a distance function. + + 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 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 L,\ d(w,l)^2 \leq d(w,l')^2 + \alpha^2 \f$ - \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 . + which leads to definitions of **weak relaxed witness complex** (or just relaxed witness complex for short) and **strong relaxed witness complex** respectively. \section Implementation + + The two complexes described above are implemented in the corresponding classes + - Gudhi::witness_complex::Witness_complex + - Gudhi::witness_complex::Strong_witness_complex + + The construction of both of them 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 internal structure Gudhi::spatial_searching::Active_witness is used internally). + 3. Construct the witness complex for nearest landmark lists. + + The constructors take on the step 1, while the function 'create_complex' executes the steps 2 and 3. - The principal class of this module is Gudhi::Witness_complex. + \section Examples - 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. + Here is an example of constructing a strong witness complex filtration and computing persistence on it: + + \include Witness_complex/example_strong_witness_persistence.cpp *\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 - \copyright GNU General Public License v3. -- cgit v1.2.3