insert sorted vertices in batch to avoid quadratic behaviour in the simplex tree

1 files changed, 7 insertions, 0 deletions

diff --git a/src/Tangential_complex/include/gudhi/Tangential_complex.h b/src/Tangential_complex/include/gudhi/Tangential_complex.h
index b448db2d..1440bfc4 100644
--- a/src/Tangential_complex/include/gudhi/Tangential_complex.h
+++ b/src/Tangential_complex/include/gudhi/Tangential_complex.h
@@ -56,6 +56,7 @@
 #include <string>
 #include <cstddef>  // for std::size_t
 #include <optional>
+#include <numeric>  // for std::iota
 
 #ifdef GUDHI_USE_TBB
 #include <tbb/parallel_for.h>
@@ -624,6 +625,12 @@ class Tangential_complex {
 
     int max_dim = -1;
 
+    // Vertices to be inserted first by the create_complex method to avoid quadratic complexity.
+    // It isn't just [0, n) if some points have multiplicity (only one copy appears in the complex).
+    std::vector<typename Simplex_tree_::Vertex_handle> vertices(m_points.size());
+    std::iota(vertices.begin(), vertices.end(), 0);
+    tree.insert_batch_vertices(vertices);
+
     // For each triangulation
     for (std::size_t idx = 0; idx < m_points.size(); ++idx) {
       // For each cell of the star