From bd4e59cb2badaad716f8e543026e452bfdbfcec7 Mon Sep 17 00:00:00 2001
From: Vincent Rouvreau <vincent.rouvreau@inria.fr>
Date: Mon, 5 Dec 2022 10:57:44 +0100
Subject: insert sorted vertices in batch to avoid quadratic behaviour in the
 simplex tree

---
 src/Tangential_complex/include/gudhi/Tangential_complex.h | 7 +++++++
 1 file changed, 7 insertions(+)

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
-- 
cgit v1.2.3