Merge last trunk modifications

git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/relaxed-witness@1683 636b058d-ea47-450e-bf9e-a15bfbe3eedb

Former-commit-id: d4af11158b5de9422f9c9820176ff10f41f89cbe

23 files changed, 389 insertions, 337 deletions

diff --git a/src/Persistent_cohomology/example/CMakeLists.txt b/src/Persistent_cohomology/example/CMakeLists.txt
index 96d3e73a..758bd6b1 100644
--- a/src/Persistent_cohomology/example/CMakeLists.txt
+++ b/src/Persistent_cohomology/example/CMakeLists.txt
@@ -30,10 +30,10 @@ endif()
 
 add_test(plain_homology ${CMAKE_CURRENT_BINARY_DIR}/plain_homology)
 add_test(persistence_from_simple_simplex_tree ${CMAKE_CURRENT_BINARY_DIR}/persistence_from_simple_simplex_tree 1 0)
-add_test(rips_persistence_3 ${CMAKE_CURRENT_BINARY_DIR}/rips_persistence ${CMAKE_SOURCE_DIR}/data/points/Kl.txt -r 0.2 -d 3 -p 3 -m 100)
-add_test(rips_persistence_via_boundary_matrix_3 ${CMAKE_CURRENT_BINARY_DIR}/rips_persistence_via_boundary_matrix ${CMAKE_SOURCE_DIR}/data/points/tore3D_1307.txt -r 0.3 -d 3 -p 3 -m 100)
-add_test(persistence_from_file_3_2_0 ${CMAKE_CURRENT_BINARY_DIR}/persistence_from_file ${CMAKE_SOURCE_DIR}/data/points/bunny_5000.st -p 2 -m 0)
-add_test(persistence_from_file_3_3_100 ${CMAKE_CURRENT_BINARY_DIR}/persistence_from_file ${CMAKE_SOURCE_DIR}/data/points/bunny_5000.st -p 3 -m 100)
+add_test(rips_persistence_3 ${CMAKE_CURRENT_BINARY_DIR}/rips_persistence ${CMAKE_SOURCE_DIR}/data/points/Kl.txt -r 0.16 -d 3 -p 3 -m 100)
+add_test(rips_persistence_via_boundary_matrix_3 ${CMAKE_CURRENT_BINARY_DIR}/rips_persistence_via_boundary_matrix ${CMAKE_SOURCE_DIR}/data/points/Kl.txt -r 0.16 -d 3 -p 3 -m 100)
+add_test(persistence_from_file_3_2_0 ${CMAKE_CURRENT_BINARY_DIR}/persistence_from_file ${CMAKE_SOURCE_DIR}/data/filtered_simplicial_complex/bunny_5000_complex.fsc -p 2 -m 0)
+add_test(persistence_from_file_3_3_100 ${CMAKE_CURRENT_BINARY_DIR}/persistence_from_file ${CMAKE_SOURCE_DIR}/data/filtered_simplicial_complex/bunny_5000_complex.fsc -p 3 -m 100)
    
 if(GMP_FOUND)
    if(GMPXX_FOUND)
@@ -45,7 +45,6 @@ if(GMP_FOUND)
         target_link_libraries(rips_multifield_persistence ${TBB_LIBRARIES})
         target_link_libraries(performance_rips_persistence ${TBB_LIBRARIES})
       endif(TBB_FOUND)
-   message("CGAL_LIBRARY = ${CGAL_LIBRARY}")
 
    add_test(rips_multifield_persistence_2_71 ${CMAKE_CURRENT_BINARY_DIR}/rips_multifield_persistence ${CMAKE_SOURCE_DIR}/data/points/Kl.txt -r 0.2 -d 3 -p 2 -q 71 -m 100)
    endif(GMPXX_FOUND)
diff --git a/src/Simplex_tree/example/CMakeLists.txt b/src/Simplex_tree/example/CMakeLists.txt
index 9314a805..e5285591 100644
--- a/src/Simplex_tree/example/CMakeLists.txt
+++ b/src/Simplex_tree/example/CMakeLists.txt
@@ -5,8 +5,10 @@ add_executable ( simplex_tree_from_cliques_of_graph simplex_tree_from_cliques_of
 if (TBB_FOUND)
   target_link_libraries(simplex_tree_from_cliques_of_graph ${TBB_LIBRARIES})
 endif()
-add_test(simplex_tree_from_cliques_of_graph_2 ${CMAKE_CURRENT_BINARY_DIR}/simplex_tree_from_cliques_of_graph ${CMAKE_SOURCE_DIR}/data/points/Klein_bottle_complex.txt 2)
-add_test(simplex_tree_from_cliques_of_graph_3 ${CMAKE_CURRENT_BINARY_DIR}/simplex_tree_from_cliques_of_graph ${CMAKE_SOURCE_DIR}/data/points/Klein_bottle_complex.txt 3)
+add_test(simplex_tree_from_cliques_of_graph_2 ${CMAKE_CURRENT_BINARY_DIR}/simplex_tree_from_cliques_of_graph
+         ${CMAKE_SOURCE_DIR}/data/filtered_simplicial_complex/Klein_bottle_complex.fsc 2)
+add_test(simplex_tree_from_cliques_of_graph_3 ${CMAKE_CURRENT_BINARY_DIR}/simplex_tree_from_cliques_of_graph
+         ${CMAKE_SOURCE_DIR}/data/filtered_simplicial_complex/Klein_bottle_complex.fsc 3)
 
 add_executable ( simple_simplex_tree simple_simplex_tree.cpp )
 if (TBB_FOUND)
@@ -20,10 +22,12 @@ add_test(mini_simplex_tree ${CMAKE_CURRENT_BINARY_DIR}/mini_simplex_tree)
 
 # An example with Simplex-tree using CGAL alpha_shapes_3
 if(GMP_FOUND AND CGAL_FOUND)
-  add_executable ( simplex_tree_from_alpha_shapes_3 simplex_tree_from_alpha_shapes_3.cpp )
-  target_link_libraries(simplex_tree_from_alpha_shapes_3 ${GMP_LIBRARIES} ${CGAL_LIBRARY} ${Boost_SYSTEM_LIBRARY})
+  add_executable ( alpha_shapes_3_simplex_tree_from_off_file example_alpha_shapes_3_simplex_tree_from_off_file.cpp )
+  target_link_libraries(alpha_shapes_3_simplex_tree_from_off_file ${GMP_LIBRARIES} ${CGAL_LIBRARY} ${Boost_SYSTEM_LIBRARY})
   if (TBB_FOUND)
-    target_link_libraries(simplex_tree_from_alpha_shapes_3 ${TBB_LIBRARIES})
+    target_link_libraries(alpha_shapes_3_simplex_tree_from_off_file ${TBB_LIBRARIES})
   endif()
-  add_test(simplex_tree_from_alpha_shapes_3 ${CMAKE_CURRENT_BINARY_DIR}/simplex_tree_from_alpha_shapes_3 ${CMAKE_SOURCE_DIR}/data/points/bunny_5000)
+  add_test(alpha_shapes_3_simplex_tree_from_off_file
+           ${CMAKE_CURRENT_BINARY_DIR}/alpha_shapes_3_simplex_tree_from_off_file
+           ${CMAKE_SOURCE_DIR}/data/points/bunny_5000.off)
 endif()
diff --git a/src/Simplex_tree/example/simplex_tree_from_alpha_shapes_3.cpp b/src/Simplex_tree/example/example_alpha_shapes_3_simplex_tree_from_off_file.cpp
index 49d358ab..ff2eebcb 100644
--- a/src/Simplex_tree/example/simplex_tree_from_alpha_shapes_3.cpp
+++ b/src/Simplex_tree/example/example_alpha_shapes_3_simplex_tree_from_off_file.cpp
@@ -20,8 +20,9 @@
  *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
  */
 
-#include <gudhi/graph_simplicial_complex.h>
 #include <gudhi/Simplex_tree.h>
+#include <gudhi/Points_3D_off_io.h>
+
 #include <boost/variant.hpp>
 
 #include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
@@ -118,24 +119,21 @@ int main(int argc, char * const argv[]) {
   // program args management
   if (argc != 2) {
     std::cerr << "Usage: " << argv[0]
-        << " path_to_file_graph \n";
+        << " path_to_off_file \n";
     return 0;
   }
 
   // Read points from file
-  std::string filegraph = argv[1];
-  std::list<Point> lp;
-  std::ifstream is(filegraph.c_str());
-  int n;
-  is >> n;
-#ifdef DEBUG_TRACES
-  std::cout << "Reading " << n << " points " << std::endl;
-#endif  // DEBUG_TRACES
-  Point p;
-  for (; n > 0; n--) {
-    is >> p;
-    lp.push_back(p);
+  std::string offInputFile(argv[1]);
+  // Read the OFF file (input file name given as parameter) and triangulate points
+  Gudhi::Points_3D_off_reader<Point> off_reader(offInputFile);
+  // Check the read operation was correct
+  if (!off_reader.is_valid()) {
+    std::cerr << "Unable to read file " << argv[1] << std::endl;
+    return 0;
   }
+  // Retrieve the triangulation
+  std::vector<Point> lp = off_reader.get_point_cloud();
 
   // alpha shape construction from points. CGAL has a strange behavior in REGULARIZED mode.
   Alpha_shape_3 as(lp.begin(), lp.end(), 0, Alpha_shape_3::GENERAL);
diff --git a/src/Spatial_searching/doc/Intro_spatial_searching.h b/src/Spatial_searching/doc/Intro_spatial_searching.h
index 2406c931..23705378 100644
--- a/src/Spatial_searching/doc/Intro_spatial_searching.h
+++ b/src/Spatial_searching/doc/Intro_spatial_searching.h
@@ -39,6 +39,10 @@ namespace spatial_searching {
  * <a target="_blank" href="http://doc.cgal.org/latest/Spatial_searching/index.html">CGAL dD spatial searching algorithms</a>.
  * It provides a simplified API to perform (approximate) neighbor searches. Contrary to CGAL default behavior, the tree
  * does not store the points themselves, but stores indices.
+ *
+ * For more details about the data structure or the algorithms, or for more advanced usages, reading 
+ * <a target="_blank" href="http://doc.cgal.org/latest/Spatial_searching/index.html">CGAL documentation</a>
+ * is highly recommended.
  * 
  * \section spatial_searching_examples Example
  * 
diff --git a/src/Spatial_searching/example/CMakeLists.txt b/src/Spatial_searching/example/CMakeLists.txt
index 3c3970d8..e73b201c 100644
--- a/src/Spatial_searching/example/CMakeLists.txt
+++ b/src/Spatial_searching/example/CMakeLists.txt
@@ -2,18 +2,12 @@ cmake_minimum_required(VERSION 2.6)
 project(Spatial_searching_examples)
 
 if(CGAL_FOUND)
-  if (NOT CGAL_VERSION VERSION_LESS 4.8.1)
-    message(STATUS "CGAL version: ${CGAL_VERSION}.")
-
+  if (NOT CGAL_VERSION VERSION_LESS 4.9.0)
     if (EIGEN3_FOUND)
       add_executable( Spatial_searching_example_spatial_searching example_spatial_searching.cpp )
       target_link_libraries(Spatial_searching_example_spatial_searching ${CGAL_LIBRARY})
-    else()
-      message(WARNING "Eigen3 not found. Version 3.1.0 is required for the Tangential_complex examples.")
+      add_test(Spatial_searching_example_spatial_searching
+               ${CMAKE_CURRENT_BINARY_DIR}/Spatial_searching_example_spatial_searching)
     endif()
-  else()
-    message(WARNING "CGAL version: ${CGAL_VERSION} is too old to compile Spatial_searching examples. Version 4.8.1 is required.")
-  endif ()
-else()
-  message(WARNING "CGAL not found. It is required for the Spatial_searching examples.")
+  endif()
 endif()
diff --git a/src/Spatial_searching/example/example_spatial_searching.cpp b/src/Spatial_searching/example/example_spatial_searching.cpp
index 7b48d055..14b324ae 100644
--- a/src/Spatial_searching/example/example_spatial_searching.cpp
+++ b/src/Spatial_searching/example/example_spatial_searching.cpp
@@ -7,12 +7,10 @@
 
 namespace gss = Gudhi::spatial_searching;
 
-int main (void)
-{
-  typedef CGAL::Epick_d<CGAL::Dimension_tag<4> >      K;
-  typedef typename K::FT                              FT;
-  typedef typename K::Point_d                         Point;
-  typedef std::vector<Point>                          Points;
+int main(void) {
+  typedef CGAL::Epick_d<CGAL::Dimension_tag<4> > K;
+  typedef typename K::Point_d Point;
+  typedef std::vector<Point> Points;
 
   typedef gss::Kd_tree_search<K, Points> Points_ds;
 
@@ -20,35 +18,35 @@ int main (void)
 
   Points points;
   for (int i = 0; i < 500; ++i)
-    points.push_back(Point(rd.get_double(-1.,1), rd.get_double(-1.,1), rd.get_double(-1.,1), rd.get_double(-1.,1)));
+    points.push_back(Point(rd.get_double(-1., 1), rd.get_double(-1., 1), rd.get_double(-1., 1), rd.get_double(-1., 1)));
 
   Points_ds points_ds(points);
 
   // 10-nearest neighbor query
   std::cout << "10 nearest neighbors from points[20]:\n";
-  auto kns_range = points_ds.query_k_nearest_neighbors(points[20], 10, true);
-  for (auto const& nghb : kns_range)
+  auto knn_range = points_ds.query_k_nearest_neighbors(points[20], 10, true);
+  for (auto const& nghb : knn_range)
     std::cout << nghb.first << " (sq. dist. = " << nghb.second << ")\n";
 
   // Incremental nearest neighbor query
   std::cout << "Incremental nearest neighbors:\n";
-  auto ins_range = points_ds.query_incremental_nearest_neighbors(points[45]);
-  // Get all the neighbors that are closer than 0.5
-  for (auto ins_iterator = ins_range.begin(); ins_iterator->second < 0.5*0.5 ; ++ins_iterator)
+  auto inn_range = points_ds.query_incremental_nearest_neighbors(points[45]);
+  // Get the neighbors in distance order until we hit the first point
+  for (auto ins_iterator = inn_range.begin(); ins_iterator->first != 0; ++ins_iterator)
     std::cout << ins_iterator->first << " (sq. dist. = " << ins_iterator->second << ")\n";
 
   // 10-farthest neighbor query
   std::cout << "10 farthest neighbors from points[20]:\n";
-  auto kfs_range = points_ds.query_k_farthest_neighbors(points[20], 10, true);
-  for (auto const& nghb : kfs_range)
+  auto kfn_range = points_ds.query_k_farthest_neighbors(points[20], 10, true);
+  for (auto const& nghb : kfn_range)
     std::cout << nghb.first << " (sq. dist. = " << nghb.second << ")\n";
 
   // Incremental farthest neighbor query
   std::cout << "Incremental farthest neighbors:\n";
-  auto ifs_range = points_ds.query_incremental_farthest_neighbors(points[45]);
-  // Get all the neighbors that are farthest than 2.3
-  for (auto ifs_iterator = ifs_range.begin(); ifs_iterator->second > 2.3*2.3 ; ++ifs_iterator)
+  auto ifn_range = points_ds.query_incremental_farthest_neighbors(points[45]);
+  // Get the neighbors in distance reverse order until we hit the first point
+  for (auto ifs_iterator = ifn_range.begin(); ifs_iterator->first != 0; ++ifs_iterator)
     std::cout << ifs_iterator->first << " (sq. dist. = " << ifs_iterator->second << ")\n";
-  
+
   return 0;
 }
diff --git a/src/Spatial_searching/include/gudhi/Kd_tree_search.h b/src/Spatial_searching/include/gudhi/Kd_tree_search.h
index ff630e9d..6728d56e 100644
--- a/src/Spatial_searching/include/gudhi/Kd_tree_search.h
+++ b/src/Spatial_searching/include/gudhi/Kd_tree_search.h
@@ -20,8 +20,8 @@
  *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
  */
 
-#ifndef GUDHI_SPATIAL_TREE_DS_H_
-#define GUDHI_SPATIAL_TREE_DS_H_
+#ifndef KD_TREE_SEARCH_H_
+#define KD_TREE_SEARCH_H_
 
 #include <CGAL/Orthogonal_k_neighbor_search.h>
 #include <CGAL/Orthogonal_incremental_neighbor_search.h>
@@ -41,22 +41,22 @@ namespace spatial_searching {
 
   /**
   * \class Kd_tree_search Kd_tree_search.h gudhi/Kd_tree_search.h
-  * \brief Spatial tree data structure to perform (approximate) nearest neighbor search.
+  * \brief Spatial tree data structure to perform (approximate) nearest and farthest neighbor search.
   *
   * \ingroup spatial_searching
   *
   * \details
   * The class Kd_tree_search is a tree-based data structure, based on
   * <a target="_blank" href="http://doc.cgal.org/latest/Spatial_searching/index.html">CGAL dD spatial searching data structures</a>.
-  * It provides a simplified API to perform (approximate) nearest neighbor searches. Contrary to CGAL default behavior, the tree
+  * It provides a simplified API to perform (approximate) nearest and farthest neighbor searches. Contrary to CGAL default behavior, the tree
   * does not store the points themselves, but stores indices.
   *
-  * There are two types of queries: the <i>k-nearest neighbor query</i>, where <i>k</i> is fixed and the <i>k</i> nearest points are 
-  * computed right away,
-  * and the <i>incremental nearest neighbor query</i>, where no number of neighbors is provided during the call, as the
+  * There are two types of queries: the <i>k-nearest or k-farthest neighbor query</i>, where <i>k</i> is fixed and the <i>k</i> nearest 
+  * or farthest points are computed right away,
+  * and the <i>incremental nearest or farthest neighbor query</i>, where no number of neighbors is provided during the call, as the
   * neighbors will be computed incrementally when the iterator on the range is incremented.
   *
-  * \tparam K must be a model of the <a target="_blank"
+  * \tparam Search_traits must be a model of the <a target="_blank"
   *   href="http://doc.cgal.org/latest/Spatial_searching/classSearchTraits.html">SearchTraits</a>
   *   concept, such as the <a target="_blank"
   *   href="http://doc.cgal.org/latest/Kernel_d/classCGAL_1_1Epick__d.html">CGAL::Epick_d</a> class, which
@@ -64,35 +64,34 @@ namespace spatial_searching {
   * \tparam Point_range is the type of the range that provides the points.
   *   It must be a range whose iterator type is a `RandomAccessIterator`.
   */
-template <typename K, typename Point_range>
-class Kd_tree_search
-{
+template <typename Search_traits, typename Point_range>
+class Kd_tree_search {
   typedef boost::iterator_property_map<
     typename Point_range::const_iterator,
     CGAL::Identity_property_map<std::ptrdiff_t> >           Point_property_map;
 
-public:
-  /// The kernel.
-  typedef K                                                 Kernel;
+ public:
+  /// The Traits.
+  typedef Search_traits                                     Traits;
   /// Number type used for distances.
-  typedef typename Kernel::FT                               FT;
+  typedef typename Traits::FT                               FT;
   /// The point type.
   typedef typename Point_range::value_type                  Point;
 
   typedef CGAL::Search_traits<
     FT, Point,
-    typename Kernel::Cartesian_const_iterator_d, 
-    typename Kernel::Construct_cartesian_const_iterator_d>  Traits_base;
-  
+    typename Traits::Cartesian_const_iterator_d,
+    typename Traits::Construct_cartesian_const_iterator_d>  Traits_base;
+
   typedef CGAL::Search_traits_adapter<
     std::ptrdiff_t,
     Point_property_map,
     Traits_base>                                            STraits;
-  
+
   typedef CGAL::Orthogonal_k_neighbor_search<STraits>       K_neighbor_search;
   typedef typename K_neighbor_search::Tree                  Tree;
   typedef typename K_neighbor_search::Distance              Distance;
-  /// \brief The range returned by a k-nearest neighbor search.
+  /// \brief The range returned by a k-nearest or k-farthest neighbor search.
   /// Its value type is `std::pair<std::size_t, FT>` where `first` is the index
   /// of a point P and `second` is the squared distance between P and the query point.
   typedef K_neighbor_search                                 KNS_range;
@@ -100,7 +99,7 @@ public:
   typedef CGAL::Orthogonal_incremental_neighbor_search<
     STraits, Distance, CGAL::Sliding_midpoint<STraits>, Tree>
                                                    Incremental_neighbor_search;
-  /// \brief The range returned by an incremental nearest neighbor search.
+  /// \brief The range returned by an incremental nearest or farthest neighbor search.
   /// Its value type is `std::pair<std::size_t, FT>` where `first` is the index
   /// of a point P and `second` is the squared distance between P and the query point.
   typedef Incremental_neighbor_search                       INS_range;
@@ -113,8 +112,7 @@ public:
     m_tree(boost::counting_iterator<std::ptrdiff_t>(0),
            boost::counting_iterator<std::ptrdiff_t>(points.size()),
            typename Tree::Splitter(),
-           STraits(std::begin(points)) )
-  {
+           STraits(std::begin(points))) {
     // Build the tree now (we don't want to wait for the first query)
     m_tree.build();
   }
@@ -132,8 +130,7 @@ public:
       m_tree(
         only_these_points.begin(), only_these_points.end(),
         typename Tree::Splitter(),
-        STraits(std::begin(points)))
-  {
+        STraits(std::begin(points))) {
     // Build the tree now (we don't want to wait for the first query)
     m_tree.build();
   }
@@ -151,16 +148,14 @@ public:
       boost::counting_iterator<std::ptrdiff_t>(begin_idx),
       boost::counting_iterator<std::ptrdiff_t>(past_the_end_idx),
       typename Tree::Splitter(),
-      STraits(std::begin(points)) )
-  {
+      STraits(std::begin(points))) {
     // Build the tree now (we don't want to wait for the first query)
     m_tree.build();
   }
 
   // Be careful, this function invalidates the tree,
   // which will be recomputed at the next query
-  void insert(std::ptrdiff_t point_idx)
-  {
+  void insert(std::ptrdiff_t point_idx) {
     m_tree.insert(point_idx);
   }
 
@@ -174,8 +169,7 @@ public:
     Point &p,
     unsigned int k,
     bool sorted = true,
-    FT eps = FT(0)) const
-  {
+    FT eps = FT(0)) const {
     // Initialize the search structure, and search all N points
     // Note that we need to pass the Distance explicitly since it needs to
     // know the property map
@@ -185,9 +179,8 @@ public:
       k,
       eps,
       true,
-      CGAL::Distance_adapter<std::ptrdiff_t,Point_property_map,CGAL::Euclidean_distance<Traits_base> >(
-        std::begin(m_points)),
-      sorted);
+      CGAL::Distance_adapter<std::ptrdiff_t, Point_property_map, CGAL::Euclidean_distance<Traits_base> >(
+        std::begin(m_points)), sorted);
 
     return search;
   }
@@ -195,11 +188,10 @@ public:
   /// \brief Search incrementally for the nearest neighbors from a query point.
   /// @param[in] p The query point.
   /// @param[in] eps Approximation factor.
-  /// @return A range containing the neighbors sorted by their distance to p. 
+  /// @return A range containing the neighbors sorted by their distance to p.
   /// All the neighbors are not computed by this function, but they will be
   /// computed incrementally when the iterator on the range is incremented.
-  INS_range query_incremental_nearest_neighbors(const Point &p, FT eps = FT(0)) const
-  {
+  INS_range query_incremental_nearest_neighbors(const Point &p, FT eps = FT(0)) const {
     // Initialize the search structure, and search all N points
     // Note that we need to pass the Distance explicitly since it needs to
     // know the property map
@@ -224,8 +216,7 @@ public:
     Point &p,
     unsigned int k,
     bool sorted = true,
-    FT eps = FT(0)) const
-  {
+    FT eps = FT(0)) const {
     // Initialize the search structure, and search all N points
     // Note that we need to pass the Distance explicitly since it needs to
     // know the property map
@@ -235,9 +226,8 @@ public:
       k,
       eps,
       false,
-      CGAL::Distance_adapter<std::ptrdiff_t,Point_property_map,CGAL::Euclidean_distance<Traits_base> >(
-        std::begin(m_points)),
-      sorted);
+      CGAL::Distance_adapter<std::ptrdiff_t, Point_property_map, CGAL::Euclidean_distance<Traits_base> >(
+        std::begin(m_points)), sorted);
 
     return search;
   }
@@ -245,11 +235,10 @@ public:
   /// \brief Search incrementally for the farthest neighbors from a query point.
   /// @param[in] p The query point.
   /// @param[in] eps Approximation factor.
-  /// @return A range containing the neighbors sorted by their distance to p. 
+  /// @return A range containing the neighbors sorted by their distance to p.
   /// All the neighbors are not computed by this function, but they will be
   /// computed incrementally when the iterator on the range is incremented.
-  INS_range query_incremental_farthest_neighbors(const Point &p, FT eps = FT(0)) const
-  {
+  INS_range query_incremental_farthest_neighbors(const Point &p, FT eps = FT(0)) const {
     // Initialize the search structure, and search all N points
     // Note that we need to pass the Distance explicitly since it needs to
     // know the property map
@@ -264,13 +253,12 @@ public:
     return search;
   }
 
-
-private:
+ private:
   Point_range const& m_points;
   Tree m_tree;
 };
 
-} // namespace spatial_searching
-} // namespace Gudhi
+}  // namespace spatial_searching
+}  // namespace Gudhi
 
-#endif // GUDHI_SPATIAL_TREE_DS_H_
+#endif  // KD_TREE_SEARCH_H_
diff --git a/src/Spatial_searching/test/CMakeLists.txt b/src/Spatial_searching/test/CMakeLists.txt
index 0f2c5ae4..7f443b79 100644
--- a/src/Spatial_searching/test/CMakeLists.txt
+++ b/src/Spatial_searching/test/CMakeLists.txt
@@ -11,20 +11,15 @@ if (GPROF_PATH)
 endif()
 
 if(CGAL_FOUND)
-  if (NOT CGAL_VERSION VERSION_LESS 4.8.1)
-    message(STATUS "CGAL version: ${CGAL_VERSION}.")
-
+  if (NOT CGAL_VERSION VERSION_LESS 4.9.0)
     if (EIGEN3_FOUND)
-
       add_executable( Spatial_searching_test_Kd_tree_search test_Kd_tree_search.cpp )
       target_link_libraries(Spatial_searching_test_Kd_tree_search 
         ${CGAL_LIBRARY} ${Boost_SYSTEM_LIBRARY} ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY})
-    else()
-      message(WARNING "Eigen3 not found. Version 3.1.0 is required for the Spatial_searching tests.")
+
+      add_test(Spatial_searching_test_Kd_tree_search ${CMAKE_CURRENT_BINARY_DIR}/Spatial_searching_test_Kd_tree_search
+      # XML format for Jenkins xUnit plugin 
+      --log_format=XML --log_sink=${CMAKE_SOURCE_DIR}/Spatial_searching_UT.xml --log_level=test_suite --report_level=no)
     endif()
-  else()
-    message(WARNING "CGAL version: ${CGAL_VERSION} is too old to compile Subsampling tests. Version 4.8.1 is required.")
   endif ()
-else()
-  message(WARNING "CGAL not found. It is required for the Spatial_searching tests.")
 endif()
diff --git a/src/Spatial_searching/test/test_Kd_tree_search.cpp b/src/Spatial_searching/test/test_Kd_tree_search.cpp
index 6f99b288..0ef22023 100644
--- a/src/Spatial_searching/test/test_Kd_tree_search.cpp
+++ b/src/Spatial_searching/test/test_Kd_tree_search.cpp
@@ -4,7 +4,7 @@
  *
  *    Author(s):       Clement Jamin
  *
- *    Copyright (C) 2016  INRIA Sophia-Antipolis (France)
+ *    Copyright (C) 2016  INRIA
  *
  *    This program is free software: you can redistribute it and/or modify
  *    it under the terms of the GNU General Public License as published by
@@ -29,38 +29,35 @@
 #include <CGAL/Epick_d.h>
 #include <CGAL/Random.h>
 
-#include <array>
 #include <vector>
 
-BOOST_AUTO_TEST_CASE(test_Kd_tree_search)
-{
-  typedef CGAL::Epick_d<CGAL::Dimension_tag<4> >    K;
-  typedef K::FT                                     FT;
-  typedef K::Point_d                                Point;
-  typedef std::vector<Point>                        Points;
+BOOST_AUTO_TEST_CASE(test_Kd_tree_search) {
+  typedef CGAL::Epick_d<CGAL::Dimension_tag<4> > K;
+  typedef K::FT FT;
+  typedef K::Point_d Point;
+  typedef std::vector<Point> Points;
 
   typedef Gudhi::spatial_searching::Kd_tree_search<
-    K, Points>                                      Points_ds;
-  
+      K, Points> Points_ds;
+
   CGAL::Random rd;
 
   Points points;
-  for (int i = 0 ; i < 500 ; ++i)
-    points.push_back(Point(rd.get_double(-1.,1), rd.get_double(-1.,1), rd.get_double(-1.,1), rd.get_double(-1.,1)));
+  for (int i = 0; i < 500; ++i)
+    points.push_back(Point(rd.get_double(-1., 1), rd.get_double(-1., 1), rd.get_double(-1., 1), rd.get_double(-1., 1)));
 
   Points_ds points_ds(points);
 
   // Test query_k_nearest_neighbors
   std::size_t closest_pt_index =
-    points_ds.query_k_nearest_neighbors(points[10], 1, false).begin()->first;
+      points_ds.query_k_nearest_neighbors(points[10], 1, false).begin()->first;
   BOOST_CHECK(closest_pt_index == 10);
 
   auto kns_range = points_ds.query_k_nearest_neighbors(points[20], 10, true);
 
   std::vector<std::size_t> knn_result;
   FT last_dist = -1.;
-  for (auto const& nghb : kns_range)
-  {
+  for (auto const& nghb : kns_range) {
     BOOST_CHECK(nghb.second > last_dist);
     knn_result.push_back(nghb.second);
     last_dist = nghb.second;
@@ -68,17 +65,16 @@ BOOST_AUTO_TEST_CASE(test_Kd_tree_search)
 
   // Test query_incremental_nearest_neighbors 
   closest_pt_index =
-    points_ds.query_incremental_nearest_neighbors(points[10]).begin()->first;
+      points_ds.query_incremental_nearest_neighbors(points[10]).begin()->first;
   BOOST_CHECK(closest_pt_index == 10);
 
-  auto ins_range = points_ds.query_incremental_nearest_neighbors(points[20]);
+  auto inn_range = points_ds.query_incremental_nearest_neighbors(points[20]);
 
   std::vector<std::size_t> inn_result;
   last_dist = -1.;
-  auto ins_it = ins_range.begin();
-  for (int i = 0 ; i < 10 ; ++ins_it, ++i)
-  {
-    auto const& nghb = *ins_it;
+  auto inn_it = inn_range.begin();
+  for (int i = 0; i < 10; ++inn_it, ++i) {
+    auto const& nghb = *inn_it;
     BOOST_CHECK(nghb.second > last_dist);
     inn_result.push_back(nghb.second);
     last_dist = nghb.second;
@@ -88,26 +84,24 @@ BOOST_AUTO_TEST_CASE(test_Kd_tree_search)
   BOOST_CHECK(knn_result == inn_result);
 
   // Test query_k_farthest_neighbors
-  auto kfs_range = points_ds.query_k_farthest_neighbors(points[20], 10, true);
+  auto kfn_range = points_ds.query_k_farthest_neighbors(points[20], 10, true);
 
   std::vector<std::size_t> kfn_result;
-  last_dist = kfs_range.begin()->second;
-  for (auto const& nghb : kfs_range)
-  {
+  last_dist = kfn_range.begin()->second;
+  for (auto const& nghb : kfn_range) {
     BOOST_CHECK(nghb.second <= last_dist);
     kfn_result.push_back(nghb.second);
     last_dist = nghb.second;
   }
 
   // Test query_k_farthest_neighbors
-  auto ifs_range = points_ds.query_incremental_farthest_neighbors(points[20]);
+  auto ifn_range = points_ds.query_incremental_farthest_neighbors(points[20]);
 
   std::vector<std::size_t> ifn_result;
-  last_dist = ifs_range.begin()->second;
-  auto ifs_it = ifs_range.begin();
-  for (int i = 0; i < 10; ++ifs_it, ++i)
-  {
-    auto const& nghb = *ifs_it;
+  last_dist = ifn_range.begin()->second;
+  auto ifn_it = ifn_range.begin();
+  for (int i = 0; i < 10; ++ifn_it, ++i) {
+    auto const& nghb = *ifn_it;
     BOOST_CHECK(nghb.second <= last_dist);
     ifn_result.push_back(nghb.second);
     last_dist = nghb.second;
diff --git a/src/Subsampling/doc/Intro_subsampling.h b/src/Subsampling/doc/Intro_subsampling.h
index f8eb2fdd..c84616dd 100644
--- a/src/Subsampling/doc/Intro_subsampling.h
+++ b/src/Subsampling/doc/Intro_subsampling.h
@@ -34,7 +34,7 @@ namespace subsampling {
  * 
  * @{
  * 
- * \section introduction Introduction
+ * \section subsamplingintroduction Introduction
  * 
  * This Gudhi component offers methods to subsample a set of points.
  * 
diff --git a/src/Subsampling/example/CMakeLists.txt b/src/Subsampling/example/CMakeLists.txt
index 81b39d6e..54349f0c 100644
--- a/src/Subsampling/example/CMakeLists.txt
+++ b/src/Subsampling/example/CMakeLists.txt
@@ -3,20 +3,18 @@ project(Subsampling_examples)
 
 if(CGAL_FOUND)
   if (NOT CGAL_VERSION VERSION_LESS 4.8.1)
-    message(STATUS "CGAL version: ${CGAL_VERSION}.")
-
     if (EIGEN3_FOUND)
+      add_executable(Subsampling_example_pick_n_random_points example_pick_n_random_points.cpp)
+      add_executable(Subsampling_example_choose_n_farthest_points example_choose_n_farthest_points.cpp)
+      add_executable(Subsampling_example_sparsify_point_set example_sparsify_point_set.cpp)
+      target_link_libraries(Subsampling_example_sparsify_point_set ${CGAL_LIBRARY})
 
-    add_executable(Subsampling_example_pick_n_random_points example_pick_n_random_points.cpp)
-    add_executable(Subsampling_example_choose_n_farthest_points example_choose_n_farthest_points.cpp)
-    add_executable(Subsampling_example_sparsify_point_set example_sparsify_point_set.cpp)
-    target_link_libraries(Subsampling_example_sparsify_point_set ${CGAL_LIBRARY})
-    else()
-      message(WARNING "Eigen3 not found. Version 3.1.0 is required for Subsampling feature.")
+      add_test(Subsampling_example_pick_n_random_points
+               ${CMAKE_CURRENT_BINARY_DIR}/Subsampling_example_pick_n_random_points)
+      add_test(Subsampling_example_choose_n_farthest_points
+               ${CMAKE_CURRENT_BINARY_DIR}/Subsampling_example_choose_n_farthest_points)
+      add_test(Subsampling_example_sparsify_point_set
+               ${CMAKE_CURRENT_BINARY_DIR}/Subsampling_example_sparsify_point_set)
     endif()
-  else()
-    message(WARNING "CGAL version: ${CGAL_VERSION} is too old to compile Subsampling examples. Version 4.8.1 is required.")
   endif ()
-else()
-  message(WARNING "CGAL not found. It is required for the Subsampling examples.")
 endif()
diff --git a/src/Subsampling/example/example_choose_n_farthest_points.cpp b/src/Subsampling/example/example_choose_n_farthest_points.cpp
index 9955d0ec..533aba74 100644
--- a/src/Subsampling/example/example_choose_n_farthest_points.cpp
+++ b/src/Subsampling/example/example_choose_n_farthest_points.cpp
@@ -3,21 +3,19 @@
 #include <CGAL/Epick_d.h>
 #include <CGAL/Random.h>
 
-#include <array>
 #include <vector>
 #include <iterator>
 
-int main (void)
-{
-  typedef CGAL::Epick_d<CGAL::Dimension_tag<4> >   K;
-  typedef typename K::FT                           FT;
-  typedef typename K::Point_d                      Point_d;
-  
+int main(void) {
+  typedef CGAL::Epick_d<CGAL::Dimension_tag<4> > K;
+  typedef typename K::Point_d Point_d;
+
   CGAL::Random rd;
 
   std::vector<Point_d> points;
-  for (int i = 0 ; i < 500 ; ++i)
-    points.push_back(Point_d(std::array<FT,4>({rd.get_double(-1.,1),rd.get_double(-1.,1),rd.get_double(-1.,1),rd.get_double(-1.,1)})));
+  for (int i = 0; i < 500; ++i)
+    points.push_back(Point_d(rd.get_double(-1., 1), rd.get_double(-1., 1),
+                             rd.get_double(-1., 1), rd.get_double(-1., 1)));
 
   K k;
   std::vector<Point_d> results;
diff --git a/src/Subsampling/example/example_pick_n_random_points.cpp b/src/Subsampling/example/example_pick_n_random_points.cpp
index d2f063ba..1e38e405 100644
--- a/src/Subsampling/example/example_pick_n_random_points.cpp
+++ b/src/Subsampling/example/example_pick_n_random_points.cpp
@@ -3,21 +3,19 @@
 #include <CGAL/Epick_d.h>
 #include <CGAL/Random.h>
 
-#include <array>
 #include <vector>
 #include <iterator>
 
-int main (void)
-{
-  typedef CGAL::Epick_d<CGAL::Dimension_tag<4> >   K;
-  typedef typename K::FT                           FT;
-  typedef typename K::Point_d                      Point_d;
-  
+int main(void) {
+  typedef CGAL::Epick_d<CGAL::Dimension_tag<4> > K;
+  typedef typename K::Point_d Point_d;
+
   CGAL::Random rd;
 
   std::vector<Point_d> points;
-  for (int i = 0 ; i < 500 ; ++i)
-    points.push_back(Point_d(std::array<FT,4>({rd.get_double(-1.,1),rd.get_double(-1.,1),rd.get_double(-1.,1),rd.get_double(-1.,1)})));
+  for (int i = 0; i < 500; ++i)
+    points.push_back(Point_d(rd.get_double(-1., 1), rd.get_double(-1., 1),
+                             rd.get_double(-1., 1), rd.get_double(-1., 1)));
 
   K k;
   std::vector<Point_d> results;
diff --git a/src/Subsampling/example/example_sparsify_point_set.cpp b/src/Subsampling/example/example_sparsify_point_set.cpp
index cb5ccf0b..b35a18d9 100644
--- a/src/Subsampling/example/example_sparsify_point_set.cpp
+++ b/src/Subsampling/example/example_sparsify_point_set.cpp
@@ -3,21 +3,19 @@
 #include <CGAL/Epick_d.h>
 #include <CGAL/Random.h>
 
-#include <array>
 #include <vector>
 #include <iterator>
 
-int main (void)
-{
-  typedef CGAL::Epick_d<CGAL::Dimension_tag<4> >   K;
-  typedef typename K::FT                           FT;
-  typedef typename K::Point_d                      Point_d;
-  
+int main(void) {
+  typedef CGAL::Epick_d<CGAL::Dimension_tag<4> > K;
+  typedef typename K::Point_d Point_d;
+
   CGAL::Random rd;
 
   std::vector<Point_d> points;
-  for (int i = 0 ; i < 500 ; ++i)
-    points.push_back(Point_d(std::array<FT,4>({rd.get_double(-1.,1),rd.get_double(-1.,1),rd.get_double(-1.,1),rd.get_double(-1.,1)})));
+  for (int i = 0; i < 500; ++i)
+    points.push_back(Point_d(rd.get_double(-1., 1), rd.get_double(-1., 1),
+                             rd.get_double(-1., 1), rd.get_double(-1., 1)));
 
   K k;
   std::vector<Point_d> results;
diff --git a/src/Subsampling/include/gudhi/choose_n_farthest_points.h b/src/Subsampling/include/gudhi/choose_n_farthest_points.h
index 8bfb38a4..40c7808d 100644
--- a/src/Subsampling/include/gudhi/choose_n_farthest_points.h
+++ b/src/Subsampling/include/gudhi/choose_n_farthest_points.h
@@ -37,89 +37,86 @@
 #include <algorithm>  // for sort
 #include <vector>
 #include <random>
+#include <limits>  // for numeric_limits<>
 
 namespace Gudhi {
 
 namespace subsampling {
-  /** 
-   *  \ingroup subsampling
-   *  \brief Subsample by a greedy strategy of iteratively adding the farthest point from the
-   *  current chosen point set to the subsampling. 
-   *  The iteration starts with the landmark `starting point`.
-   *  \details It chooses `final_size` points from a random access range `input_pts` and
-   *  outputs it in the output iterator `output_it`.
-   *  
-   */
-
-  template < typename Kernel,
-             typename Point_container,
-             typename OutputIterator>
-  void choose_n_farthest_points( Kernel const &k,
-                                 Point_container const &input_pts,
-                                 unsigned final_size,
-                                 unsigned starting_point,
-                                 OutputIterator output_it)
-  {
-    typename Kernel::Squared_distance_d sqdist = k.squared_distance_d_object();
-    
-    int nb_points = boost::size(input_pts);
-    assert(nb_points >= final_size);
-
-    unsigned current_number_of_landmarks = 0;  // counter for landmarks
+
+/** 
+ *  \ingroup subsampling
+ *  \brief Subsample by a greedy strategy of iteratively adding the farthest point from the
+ *  current chosen point set to the subsampling. 
+ *  The iteration starts with the landmark `starting point`.
+ *  \details It chooses `final_size` points from a random access range `input_pts` and
+ *  outputs it in the output iterator `output_it`.
+ *  
+ */
+template < typename Kernel,
+typename Point_container,
+typename OutputIterator>
+void choose_n_farthest_points(Kernel const &k,
+                              Point_container const &input_pts,
+                              std::size_t final_size,
+                              std::size_t starting_point,
+                              OutputIterator output_it) {
+  typename Kernel::Squared_distance_d sqdist = k.squared_distance_d_object();
+
+  std::size_t nb_points = boost::size(input_pts);
+  assert(nb_points >= final_size);
+
+  std::size_t current_number_of_landmarks = 0;  // counter for landmarks
+  const double infty = std::numeric_limits<double>::infinity();  // infinity (see next entry)
+  std::vector< double > dist_to_L(nb_points, infty);  // vector of current distances to L from input_pts
+
+  std::size_t curr_max_w = starting_point;
+
+  for (current_number_of_landmarks = 0; current_number_of_landmarks != final_size; current_number_of_landmarks++) {
+    // curr_max_w at this point is the next landmark
+    *output_it++ = input_pts[curr_max_w];
+    std::size_t i = 0;
+    for (auto& p : input_pts) {
+      double curr_dist = sqdist(p, *(std::begin(input_pts) + curr_max_w));
+      if (curr_dist < dist_to_L[i])
+        dist_to_L[i] = curr_dist;
+      ++i;
+    }
+    // choose the next curr_max_w
     double curr_max_dist = 0;  // used for defining the furhest point from L
-    const double infty = std::numeric_limits<double>::infinity();  // infinity (see next entry)
-    std::vector< double > dist_to_L(nb_points, infty);  // vector of current distances to L from input_pts
-
-    int curr_max_w = starting_point;
-
-    for (current_number_of_landmarks = 0; current_number_of_landmarks != final_size; current_number_of_landmarks++) {
-      // curr_max_w at this point is the next landmark
-      *output_it++ = input_pts[curr_max_w];
-      // std::cout << curr_max_w << "\n";
-      unsigned i = 0;
-      for (auto& p : input_pts) {
-        double curr_dist = sqdist(p, *(std::begin(input_pts) + curr_max_w));
-        if (curr_dist < dist_to_L[i])
-          dist_to_L[i] = curr_dist;
-        ++i;
+    for (i = 0; i < dist_to_L.size(); i++)
+      if (dist_to_L[i] > curr_max_dist) {
+        curr_max_dist = dist_to_L[i];
+        curr_max_w = i;
       }
-      // choose the next curr_max_w
-      curr_max_dist = 0;
-      for (i = 0; i < dist_to_L.size(); i++)
-        if (dist_to_L[i] > curr_max_dist) {
-          curr_max_dist = dist_to_L[i];
-          curr_max_w = i;
-        }
-    }
-  }
-  
-  /** 
-   *  \ingroup subsampling
-   *  \brief Subsample by a greedy strategy of iteratively adding the farthest point from the
-   *  current chosen point set to the subsampling. 
-   *  The iteration starts with a random landmark.
-   *  \details It chooses `final_size` points from a random access range `input_pts` and
-   *  outputs it in the output iterator `output_it`.
-   *  
-   */
-  template < typename Kernel,
-             typename Point_container,
-             typename OutputIterator>
-  void choose_n_farthest_points( Kernel& k,
-                                 Point_container const &input_pts,
-                                 int final_size,
-                                 OutputIterator output_it)
-  {
-    // Choose randomly the first landmark 
-    std::random_device rd;
-    std::mt19937 gen(rd());
-    std::uniform_int_distribution<> dis(1, 6);
-    int starting_point = dis(gen);
-    choose_n_farthest_points(k, input_pts, final_size, starting_point, output_it);
   }
-  
-} // namespace subsampling
-  
+}
+
+/** 
+ *  \ingroup subsampling
+ *  \brief Subsample by a greedy strategy of iteratively adding the farthest point from the
+ *  current chosen point set to the subsampling. 
+ *  The iteration starts with a random landmark.
+ *  \details It chooses `final_size` points from a random access range `input_pts` and
+ *  outputs it in the output iterator `output_it`.
+ *  
+ */
+template < typename Kernel,
+typename Point_container,
+typename OutputIterator>
+void choose_n_farthest_points(Kernel const& k,
+                              Point_container const &input_pts,
+                              unsigned final_size,
+                              OutputIterator output_it) {
+  // Choose randomly the first landmark
+  std::random_device rd;
+  std::mt19937 gen(rd());
+  std::uniform_int_distribution<> dis(1, 6);
+  int starting_point = dis(gen);
+  choose_n_farthest_points(k, input_pts, final_size, starting_point, output_it);
+}
+
+}  // namespace subsampling
+
 }  // namespace Gudhi
 
 #endif  // CHOOSE_N_FARTHEST_POINTS_H_
diff --git a/src/Subsampling/include/gudhi/pick_n_random_points.h b/src/Subsampling/include/gudhi/pick_n_random_points.h
index 4ca1fafc..e89b2b2d 100644
--- a/src/Subsampling/include/gudhi/pick_n_random_points.h
+++ b/src/Subsampling/include/gudhi/pick_n_random_points.h
@@ -20,63 +20,65 @@
  *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
  */
 
-#ifndef PICK_RANDOM_POINTS_H_
-#define PICK_RANDOM_POINTS_H_
+#ifndef PICK_N_RANDOM_POINTS_H_
+#define PICK_N_RANDOM_POINTS_H_
+
+#include <gudhi/Clock.h>
 
 #include <boost/range/size.hpp>
 
+#include <cstddef>
 #include <random>     // random_device, mt19937
 #include <algorithm>  // shuffle
 #include <numeric>    // iota
 #include <iterator>
-#include <gudhi/Clock.h>
+#include <vector>
 
 
 namespace Gudhi {
 
 namespace subsampling {
-  
-  /**
-   *  \ingroup subsampling
-   * \brief Subsample a point set by picking random vertices.
-   *
-   *  \details It chooses `final_size` distinct points from a random access range `points`
-   *  and outputs them to the output iterator `output_it`.
-   *  Point_container::iterator should be ValueSwappable and RandomAccessIterator.
-   */
-
-  template <typename Point_container,
-            typename OutputIterator>
-  void pick_n_random_points(Point_container const &points,
-                          unsigned final_size,
+
+/**
+ *  \ingroup subsampling
+ * \brief Subsample a point set by picking random vertices.
+ *
+ *  \details It chooses `final_size` distinct points from a random access range `points`
+ *  and outputs them to the output iterator `output_it`.
+ *  Point_container::iterator should be ValueSwappable and RandomAccessIterator.
+ */
+template <typename Point_container,
+typename OutputIterator>
+void pick_n_random_points(Point_container const &points,
+                          std::size_t final_size,
                           OutputIterator output_it) {
 #ifdef GUDHI_SUBS_PROFILING
-    Gudhi::Clock t;
+  Gudhi::Clock t;
 #endif
 
-    unsigned nbP = boost::size(points);
-    assert(nbP >= final_size);
-    std::vector<int> landmarks(nbP);
-    std::iota(landmarks.begin(), landmarks.end(), 0);
+  std::size_t nbP = boost::size(points);
+  assert(nbP >= final_size);
+  std::vector<int> landmarks(nbP);
+  std::iota(landmarks.begin(), landmarks.end(), 0);
+
+  std::random_device rd;
+  std::mt19937 g(rd());
 
-    std::random_device rd;
-    std::mt19937 g(rd());
- 
-    std::shuffle(landmarks.begin(), landmarks.end(), g);
-    landmarks.resize(final_size);
+  std::shuffle(landmarks.begin(), landmarks.end(), g);
+  landmarks.resize(final_size);
+
+  for (int l : landmarks)
+    *output_it++ = points[l];
 
-    for (int l: landmarks)
-      *output_it++ = points[l];
-    
 #ifdef GUDHI_SUBS_PROFILING
-    t.end();
-    std::cerr << "Random landmark choice took " << t.num_seconds()
+  t.end();
+  std::cerr << "Random landmark choice took " << t.num_seconds()
       << " seconds." << std::endl;
 #endif
-  }
+}
+
+}  // namespace subsampling
 
-} // namesapce subsampling
-  
 }  // namespace Gudhi
 
-#endif  // PICK_RANDOM_POINTS_H_
+#endif  // PICK_N_RANDOM_POINTS_H_
diff --git a/src/Subsampling/include/gudhi/sparsify_point_set.h b/src/Subsampling/include/gudhi/sparsify_point_set.h
index 607555b4..7ff11b4c 100644
--- a/src/Subsampling/include/gudhi/sparsify_point_set.h
+++ b/src/Subsampling/include/gudhi/sparsify_point_set.h
@@ -20,8 +20,8 @@
  *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
  */
 
-#ifndef GUDHI_SPARSIFY_POINT_SET_H
-#define GUDHI_SPARSIFY_POINT_SET_H
+#ifndef SPARSIFY_POINT_SET_H_
+#define SPARSIFY_POINT_SET_H_
 
 #include <gudhi/Kd_tree_search.h>
 #ifdef GUDHI_SUBSAMPLING_PROFILING
@@ -32,6 +32,7 @@
 #include <vector>
 
 namespace Gudhi {
+
 namespace subsampling {
 
 /**
@@ -54,16 +55,14 @@ namespace subsampling {
  * @param[in] min_squared_dist Minimum squared distance separating the output points.
  * @param[out] output_it The output iterator.
  */
-
 template <typename Kernel, typename Point_range, typename OutputIterator>
 void
 sparsify_point_set(
-  const Kernel &k, Point_range const& input_pts,
-  typename Kernel::FT min_squared_dist,
-  OutputIterator output_it)
-{ 
+                   const Kernel &k, Point_range const& input_pts,
+                   typename Kernel::FT min_squared_dist,
+                   OutputIterator output_it) {
   typedef typename Gudhi::spatial_searching::Kd_tree_search<
-    Kernel, Point_range>  Points_ds;
+      Kernel, Point_range> Points_ds;
 
   typename Kernel::Squared_distance_d sqdist = k.squared_distance_d_object();
 
@@ -78,10 +77,9 @@ sparsify_point_set(
   // Parse the input points, and add them if they are not too close to
   // the other points
   std::size_t pt_idx = 0;
-  for (typename Point_range::const_iterator it_pt = input_pts.begin() ;
-    it_pt != input_pts.end();
-    ++it_pt, ++pt_idx)
-  {
+  for (typename Point_range::const_iterator it_pt = input_pts.begin();
+       it_pt != input_pts.end();
+       ++it_pt, ++pt_idx) {
     if (dropped_points[pt_idx])
       continue;
 
@@ -90,30 +88,28 @@ sparsify_point_set(
     auto ins_range = points_ds.query_incremental_nearest_neighbors(*it_pt);
 
     // If another point Q is closer that min_squared_dist, mark Q to be dropped
-    for (auto const& neighbor : ins_range)
-    {
+    for (auto const& neighbor : ins_range) {
       std::size_t neighbor_point_idx = neighbor.first;
       // If the neighbor is too close, we drop the neighbor
-      if (neighbor.second < min_squared_dist)
-      {
-        // N.B.: If neighbor_point_idx < pt_idx, 
+      if (neighbor.second < min_squared_dist) {
+        // N.B.: If neighbor_point_idx < pt_idx,
         // dropped_points[neighbor_point_idx] is already true but adding a
         // test doesn't make things faster, so why bother?
         dropped_points[neighbor_point_idx] = true;
-      }
-      else
+      } else {
         break;
+      }
     }
   }
 
 #ifdef GUDHI_SUBSAMPLING_PROFILING
   t.end();
   std::cerr << "Point set sparsified in " << t.num_seconds()
-    << " seconds." << std::endl;
+      << " seconds." << std::endl;
 #endif
 }
 
-} // namespace subsampling
-} // namespace Gudhi
+}  // namespace subsampling
+}  // namespace Gudhi
 
-#endif // GUDHI_POINT_CLOUD_H
+#endif  // SPARSIFY_POINT_SET_H_
diff --git a/src/Subsampling/test/CMakeLists.txt b/src/Subsampling/test/CMakeLists.txt
index 91d4ed8f..3a2fb649 100644
--- a/src/Subsampling/test/CMakeLists.txt
+++ b/src/Subsampling/test/CMakeLists.txt
@@ -12,8 +12,6 @@ endif()
 
 if(CGAL_FOUND)
   if (NOT CGAL_VERSION VERSION_LESS 4.8.1)
-    message(STATUS "CGAL version: ${CGAL_VERSION}.")
-
     if (EIGEN3_FOUND)
       add_executable( Subsampling_test_pick_n_random_points test_pick_n_random_points.cpp )
       target_link_libraries(Subsampling_test_pick_n_random_points ${CGAL_LIBRARY} ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY})
@@ -23,12 +21,18 @@ if(CGAL_FOUND)
 
       add_executable(Subsampling_test_sparsify_point_set test_sparsify_point_set.cpp)
       target_link_libraries(Subsampling_test_sparsify_point_set ${CGAL_LIBRARY} ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY})
-    else()
-      message(WARNING "Eigen3 not found. Version 3.1.0 is required for Subsampling feature.")
+
+      add_test(Subsampling_test_pick_n_random_points ${CMAKE_CURRENT_BINARY_DIR}/Subsampling_test_pick_n_random_points
+      # XML format for Jenkins xUnit plugin 
+      --log_format=XML --log_sink=${CMAKE_SOURCE_DIR}/Subsampling_test_pick_n_random_points_UT.xml --log_level=test_suite --report_level=no)
+
+      add_test(Subsampling_test_choose_n_farthest_points ${CMAKE_CURRENT_BINARY_DIR}/Subsampling_test_choose_n_farthest_points
+      # XML format for Jenkins xUnit plugin 
+      --log_format=XML --log_sink=${CMAKE_SOURCE_DIR}/Subsampling_test_choose_n_farthest_points_UT.xml --log_level=test_suite --report_level=no)
+
+      add_test(Subsampling_test_sparsify_point_set ${CMAKE_CURRENT_BINARY_DIR}/Subsampling_test_sparsify_point_set
+      # XML format for Jenkins xUnit plugin 
+      --log_format=XML --log_sink=${CMAKE_SOURCE_DIR}/Subsampling_test_sparsify_point_set_UT.xml --log_level=test_suite --report_level=no)
     endif()
-  else()
-    message(WARNING "CGAL version: ${CGAL_VERSION} is too old to compile Subsampling tests. Version 4.8.1 is required.")
   endif ()
-else()
-  message(WARNING "CGAL not found. It is required for the Subsampling tests.")
 endif()
diff --git a/src/Subsampling/test/test_choose_n_farthest_points.cpp b/src/Subsampling/test/test_choose_n_farthest_points.cpp
index f79a4dfb..d064899a 100644
--- a/src/Subsampling/test/test_choose_n_farthest_points.cpp
+++ b/src/Subsampling/test/test_choose_n_farthest_points.cpp
@@ -35,10 +35,9 @@
 
 #include <CGAL/Epick_d.h>
 
-typedef CGAL::Epick_d<CGAL::Dynamic_dimension_tag>                K;
-typedef typename K::FT                                            FT;
-typedef typename K::Point_d                                       Point_d;
-
+typedef CGAL::Epick_d<CGAL::Dynamic_dimension_tag> K;
+typedef typename K::FT FT;
+typedef typename K::Point_d Point_d;
 
 BOOST_AUTO_TEST_CASE(test_choose_farthest_point) {
   std::vector< Point_d > points, landmarks;
@@ -52,6 +51,6 @@ BOOST_AUTO_TEST_CASE(test_choose_farthest_point) {
   landmarks.clear();
   K k;
   Gudhi::subsampling::choose_n_farthest_points(k, points, 100, std::back_inserter(landmarks));
-  
+
   BOOST_CHECK(landmarks.size() == 100);
 }
diff --git a/src/Subsampling/test/test_sparsify_point_set.cpp b/src/Subsampling/test/test_sparsify_point_set.cpp
index 61f6fa18..f993d6d6 100644
--- a/src/Subsampling/test/test_sparsify_point_set.cpp
+++ b/src/Subsampling/test/test_sparsify_point_set.cpp
@@ -29,21 +29,19 @@
 #include <CGAL/Epick_d.h>
 #include <CGAL/Random.h>
 
-#include <array>
 #include <vector>
 #include <iterator>
 
 BOOST_AUTO_TEST_CASE(test_sparsify_point_set) 
 {
   typedef CGAL::Epick_d<CGAL::Dimension_tag<4> >   K;
-  typedef typename K::FT                           FT;
   typedef typename K::Point_d                      Point_d;
   
   CGAL::Random rd;
 
   std::vector<Point_d> points;
   for (int i = 0 ; i < 500 ; ++i)
-    points.push_back(Point_d(std::array<FT,4>({rd.get_double(-1.,1),rd.get_double(-1.,1),rd.get_double(-1.,1),rd.get_double(-1.,1)})));
+    points.push_back(Point_d(rd.get_double(-1.,1),rd.get_double(-1.,1),rd.get_double(-1.,1),rd.get_double(-1.,1)));
 
   K k;
   std::vector<Point_d> results;
diff --git a/src/Witness_complex/include/gudhi/Construct_closest_landmark_table.h b/src/Witness_complex/include/gudhi/Construct_closest_landmark_table.h
new file mode 100644
index 00000000..ef711c34
--- /dev/null
+++ b/src/Witness_complex/include/gudhi/Construct_closest_landmark_table.h
@@ -0,0 +1,90 @@
+/*    This file is part of the Gudhi Library. The Gudhi library
+ *    (Geometric Understanding in Higher Dimensions) is a generic C++
+ *    library for computational topology.
+ *
+ *    Author(s):       Siargey Kachanovich
+ *
+ *    Copyright (C) 2015  INRIA Sophia Antipolis-Méditerranée (France)
+ *
+ *    This program is free software: you can redistribute it and/or modify
+ *    it under the terms of the GNU General Public License as published by
+ *    the Free Software Foundation, either version 3 of the License, or
+ *    (at your option) any later version.
+ *
+ *    This program is distributed in the hope that it will be useful,
+ *    but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *    GNU General Public License for more details.
+ *
+ *    You should have received a copy of the GNU General Public License
+ *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#ifndef CONSTRUCT_CLOSEST_LANDMARK_TABLE_H_
+#define CONSTRUCT_CLOSEST_LANDMARK_TABLE_H_
+
+#include <boost/range/size.hpp>
+
+#include <queue>  // for priority_queue<>
+#include <utility>  // for pair<>
+#include <iterator>
+#include <vector>
+#include <set>
+
+namespace Gudhi {
+
+namespace witness_complex {
+
+  /**
+   *  \ingroup witness_complex
+   * \brief Construct the closest landmark tables for all witnesses.
+   *  \details Output a table 'knn', each line of which represents a witness and
+   *   consists of landmarks sorted by
+   *   euclidean distance from the corresponding witness.
+   *
+   *  The type WitnessContainer is a random access range and
+   *  the type LandmarkContainer is a range.
+   *  The type KNearestNeighbors can be seen as 
+   *  Witness_range<Closest_landmark_range<Vertex_handle>>, where
+   *  Witness_range and Closest_landmark_range are random access ranges and
+   *  Vertex_handle is the label type of a vertex in a simplicial complex.
+   *  Closest_landmark_range needs to have push_back operation.
+   */
+
+  template <typename WitnessContainer,
+            typename LandmarkContainer,
+            typename KNearestNeighbours>
+  void construct_closest_landmark_table(WitnessContainer const &points,
+                                        LandmarkContainer const &landmarks,
+                                        KNearestNeighbours &knn) {
+    int nbP = boost::size(points);
+    assert(nbP >= boost::size(landmarks));
+
+    int dim = boost::size(*std::begin(points));
+    typedef std::pair<double, int> dist_i;
+    typedef bool (*comp)(dist_i, dist_i);
+    knn = KNearestNeighbours(nbP);
+    for (int points_i = 0; points_i < nbP; points_i++) {
+      std::priority_queue<dist_i, std::vector<dist_i>, comp> l_heap([](dist_i j1, dist_i j2) {
+          return j1.first > j2.first;
+        });
+      typename LandmarkContainer::const_iterator landmarks_it;
+      int landmarks_i = 0;
+      for (landmarks_it = landmarks.begin(), landmarks_i = 0; landmarks_it != landmarks.end();
+           ++landmarks_it, landmarks_i++) {
+        dist_i dist = std::make_pair(euclidean_distance(points[points_i], *landmarks_it), landmarks_i);
+        l_heap.push(dist);
+      }
+      for (int i = 0; i < dim + 1; i++) {
+        dist_i dist = l_heap.top();
+        knn[points_i].push_back(dist.second);
+        l_heap.pop();
+      }
+    }
+  }
+
+}  // namespace witness_complex
+
+}  // namespace Gudhi
+
+#endif  // CONSTRUCT_CLOSEST_LANDMARK_TABLE_H_
diff --git a/src/cmake/modules/FindQGLViewer.cmake b/src/cmake/modules/FindQGLViewer.cmake
index 65723d67..1f3dbc1f 100644
--- a/src/cmake/modules/FindQGLViewer.cmake
+++ b/src/cmake/modules/FindQGLViewer.cmake
@@ -15,7 +15,7 @@ find_path(QGLVIEWER_INCLUDE_DIR
          )
 
 find_library(QGLVIEWER_LIBRARY_RELEASE 
-             NAMES qglviewer-qt4 qglviewer QGLViewer QGLViewer2
+             NAMES qglviewer-qt4 QGLViewer-qt4 qglviewer QGLViewer QGLViewer2
              PATHS /usr/lib
                    /usr/local/lib
                    ENV QGLVIEWERROOT
diff --git a/src/cmake/modules/GUDHI_user_version_target.txt b/src/cmake/modules/GUDHI_user_version_target.txt
index 805f0a83..0ab36cfc 100644
--- a/src/cmake/modules/GUDHI_user_version_target.txt
+++ b/src/cmake/modules/GUDHI_user_version_target.txt
@@ -48,7 +48,7 @@ if (NOT CMAKE_VERSION VERSION_LESS 2.8.11)
   add_custom_command(TARGET user_version PRE_BUILD COMMAND ${CMAKE_COMMAND} -E
                      copy_directory ${CMAKE_SOURCE_DIR}/src/GudhUI ${GUDHI_USER_VERSION_DIR}/GudhUI)
   
-  set(GUDHI_MODULES "common;Alpha_complex;Bitmap_cubical_complex;Contraction;Hasse_complex;Persistent_cohomology;Simplex_tree;Skeleton_blocker;Witness_complex")
+  set(GUDHI_MODULES "common;Alpha_complex;Bitmap_cubical_complex;Contraction;Hasse_complex;Persistent_cohomology;Simplex_tree;Skeleton_blocker;Spatial_searching;Subsampling;Witness_complex")
   
   foreach(GUDHI_MODULE ${GUDHI_MODULES})
     # doc files