Faster, Deterministic and Space Efficient Subtrajectory Clustering

We present a bicriteria approximation algorithm that uses $𝒪(k{n}^3{\log }^{4}n)$ time and $𝒪(n^3)$ space, and computes an $(\mathrm{\ell },4\mathrm{\Delta })$-clustering of size $𝒪(k\log n)$. When compared to previous works [3, 13, 5] our results:

• $\mathrm{■}$

  obtain deterministic results and improve the running time by a factor near-linear in $\mathrm{\ell }$,

• $\mathrm{■}$

  match the space usage,

• $\mathrm{■}$

  improve the approximation in $\mathrm{\Delta }$ from a factor $11$ to $4$,

• $\mathrm{■}$

  asymptotically match the clustering size (whenever $\mathrm{\ell }\in \mathrm{\Omega }(\log n/\log k)$).

Compared exclusively to deterministic results [13], we instead improve time by a factor near-linear in $n\mathrm{\ell }$, space by a factor super-linear in $n\mathrm{\ell }$, and obtain asymptotically equal clustering size for all $\mathrm{\ell }$ (see also Table 1).

Our algorithm constructs a clustering iteratively by greedily adding a cluster that covers an approximately-maximum set of uncovered points on $T$. The challenge is to compute such a cluster. Previous work [5, 3] presented randomized algorithms for constructing a cluster based on $\epsilon$-net sampling over the set of all candidate clusters. They shatter the set of candidate clusters and show that it has bounded VC dimension, which leads to their asymptotic approximation of $k$ – the minimum size of an $(\mathrm{\ell },\mathrm{\Delta })$-clustering. The algorithm of Conradi and Driemel [13] is more similar to ours. They also simplify the input and iteratively select the cluster with the (exact) maximum coverage to obtain an $(\mathrm{\ell },\mathrm{\Delta })$-clustering of size $𝒪(k\log n)$. The key difference lies in finding the next cluster. Conradi and Driemel [13] explicitly consider a set of $𝒪(n^3\mathrm{\ell })$ candidate clusters, which requires $𝒪(n^4\mathrm{\ell })$ time and space to construct.

We make two key contributions that distinguish us from prior works: First, we present a novel simplification algorithm that computes a curve $S$ such that we may restrict potential reference curves of clusters to be subcurves of $S$. This new curve simplification technique allows us to create a clustering where clusters have radius at most $4\mathrm{\Delta }$ as opposed to $11\mathrm{\Delta }$. Second, we prove that we may restrict the reference curves to be one of two types:

• $\mathrm{■}$

  vertex-subcurves of $S$, which are subcurves that start and end at a vertex of $S$,
  (we may furthermore only consider subcurves whose complexity is a power of $2$)

• $\mathrm{■}$

  and subedges of $S$, which are subcurves that are a subsegment of a single edge of $S$.

We prove that a greedy algorithm that exclusively adds maximal clusters where the reference curve is of one of these two types creates a clustering of size $𝒪(k\log n)$. This characterization reduces the set of candidate clusters from $\widetilde{𝒪}(n^3\mathrm{\ell })$ to $\widetilde{𝒪}(n^2)$ which significantly reduces the time spent compared to [13]. The geometric characterization of these subcurves allow us to compute candidate clusters on the fly, significantly reducing space usage.

A reparameterization of $[1,n]$ is a non-decreasing surjection $f:[0,1]\to [1,n]$. Two reparameterizations $f$ and $g$ of $[1,m]$ and $[1,n]$, respectively, describe a matching $(f,g)$ between two curves $P$ and $Q$ with $n$ and $m$ vertices, where for any $t\in [0,1]$, point $P(f(t))$ is matched to $Q(g(t))$. A matching $(f,g)$ is said to have cost ${\max }_t\parallel P(f(t))-Q(g(t))\parallel ,$ where $\parallel \cdot \parallel$ denotes the Euclidean norm. A matching with cost at most $\mathrm{\Delta }$ is called a $\mathrm{\Delta }$-matching. The (continuous) Fréchet distance $d_F(P,Q)$ between $P$ and $Q$ is the minimum cost over all matchings.

The parameter space of curves $P$ and $Q$ with $m$ and $n$ vertices, respectively, is given by the orthogonal rectangle $[1,m]\times [1,n]$. This parameter space is associated with a regular grid whose cells are the squares $[i,i+1]\times [j,j+1]$ for integers $i$ and $j$. A point $(x,y)$ in the parameter space corresponds to the pair of points $P(x)$ and $Q(y)$. We say that $(x,y)$ is $\mathrm{\Delta }$-free if $\parallel P(x)-Q(y)\parallel \le \mathrm{\Delta }$. The $\mathrm{\Delta }$-free space diagram $\mathrm{\Delta }-\mathrm{FSD}(P,Q)$ of $P$ and $Q$ is the set of $\mathrm{\Delta }$-free points in the parameter space of $P$ and $Q$. The obstacles of $\mathrm{\Delta }-\mathrm{FSD}(P,Q)$ are the connected components of $([1,m]\times [1,n])\setminus \mathrm{\Delta }-\mathrm{FSD}(P,Q)$.

Alt and Godau [4] observe that the Fréchet distance between $P[x_1,x_2]$ and $Q[y_1,y_2]$ is at most $\mathrm{\Delta }$ if and only if there is a bimonotone path in $\mathrm{\Delta }-\mathrm{FSD}(P,Q)$ from $(x_1,y_1)$ to $(x_2,y_2)$ (and $x_1\le x_2$ and $y_1\le y_2$).

Our input is a curve $T$ with $n$ vertices, which we will call the trajectory, some integer parameter $\mathrm{\ell }\ge 2$, and some distance parameter $\mathrm{\Delta }\ge 0$. We consider clustering subtrajectories of $T$ using pathlets:

We can see a pathlet $(P,ℐ)$ as a cluster, where the center is $P$ and all subtrajectories induced by $ℐ$ get mapped to $P$. See Figure 1. An $(\mathrm{\ell },\mathrm{\Delta })$-clustering of $T$ is defined as follows:

Throughout this paper, we let $k_{\mathrm{\ell }}(\mathrm{\Delta })$ denote the smallest integer for which there exists an $(\mathrm{\ell },\mathrm{\Delta })$-clustering of size $k_{\mathrm{\ell }}(\mathrm{\Delta })$. The goal is to find an $(\mathrm{\ell },{\mathrm{\Delta }}^{\prime })$-clustering $C$ where $|C|$ is not too large compared to $k_{\mathrm{\ell }}(\mathrm{\Delta })$, and ${\mathrm{\Delta }}^{\prime }\in 𝒪(\mathrm{\Delta })$.

We define a Universe $𝒰$ as any set of interior-disjoint closed intervals that together cover $[1,n]$. Given a fixed universe $𝒰$, we can weigh each pathlet by what we call its coverage:

Whenever $𝒰$ is clear from context we denote the coverage of a pathlet $(P,ℐ)$ by $\mathrm{Cov}(P,ℐ)$.

We introduce the reachability graph in Section 7. This graph is defined on a subcurve $W$ of $S$ and a set $Z$ of points in ${\mathrm{\Delta }}^{\prime }-\mathrm{FSD}(W,T)$. The reachability graph $G(W,T,Z)$ is a directed acyclic graph whose vertices are the set of points $Z$, together with certain boundary points of the free space ${\mathrm{\Delta }}^{\prime }-\mathrm{FSD}(W,T)$ and a collection of steiner points. Given two points $(x,y)$ and $(x^{\prime },y^{\prime })$ in $Z$, the graph contains a directed path from $(x,y)$ to $(x^{\prime },y^{\prime })$ if and only if $d_F(W[x,x^{\prime }],T[y,y^{\prime }])\le {\mathrm{\Delta }}^{\prime }$.

We treat the free space diagram as a rectilinear polygon $ℛ$ with rectilinear holes, obtained by reducing all obstacles of ${\mathrm{\Delta }}^{\prime }-\mathrm{FSD}(W,T)$ to their intersections with the parameter space grid. We show that a bimonotone path between two points $p$ and $q$ exists in ${\mathrm{\Delta }}^{\prime }-\mathrm{FSD}(W,T)$ if and only if a rectilinear shortest path between $p$ and $q$ in $ℛ$ has length ${\parallel p-q\parallel }_1$, the $L_1$-distance between $p$ and $q$. The reachability graph $G(W,T,Z)$ is defined as the shortest paths preserving graph [20] for the set $Z$ with respect to $ℛ$, made into a directed graph by directing edges, which are all horizontal or vertical, to the right or top. This graph has $𝒪((|W|n+|Z|)\log (n|Z|))$ complexity, and a shortest path in the graph between points in $Z$ is also a rectilinear shortest path between the corresponding points in $ℛ$.

In Section 8 we construct a pathlet where the reference curve is a vertex subcurve of $S$. For a given vertex $S(i)$ of $S$, we construct reference-optimal $(\mathrm{\ell },{\mathrm{\Delta }}^{\prime })$-pathlets $(S[i,i+j],{ℐ}_j)$ for all $j\in [\mathrm{\ell }]$. We first identify a set $Z$ of $𝒪(n\mathrm{\ell })$ critical points in ${\mathrm{\Delta }}^{\prime }-\mathrm{FSD}(S[i,i+\mathrm{\ell }],T)$. We show that for every reference curve $S[i,i+j]$, there is a reference-optimal $(\mathrm{\ell },{\mathrm{\Delta }}^{\prime })$-pathlet $(S[i,i+j],{ℐ}_j)$ where for each interval $[y,y^{\prime }]\in {ℐ}_j$, the points $(i,y)$ and $(i+j,y^{\prime })$ are critical points. We construct the intervals ${ℐ}_j$ through a sweepline algorithm over the reachability graph $G(S[i,i+\mathrm{\ell }],T,Z)$, which has $𝒪(n\mathrm{\ell }\log n)$ complexity. Our sweepline computes, for all $j\in [\mathrm{\ell }]$, a reference-optimal $(j,{\mathrm{\Delta }}^{\prime })$-pathlet $(S[i,i+j],{ℐ}_j)$ by iterating over all in-edges to critical points $(i+j,y)$ in $G(S[i,i+\mathrm{\ell }],T,Z)$. Doing this for all $i$ (and remembering the optimum) thereby takes $𝒪(n^2\mathrm{\ell }{\log }^{2}n)$ time and $𝒪(n\mathrm{\ell }\log n)$ space.

In Section 9 we construct a pathlet where the reference curve is a subsegment of an edge of $S$. For a given edge $e$ of $S$, we again first identify a set $Z$ of $𝒪(n^2)$ critical points in ${\mathrm{\Delta }}^{\prime }-\mathrm{FSD}(e,T)$. However, rather than restricting the intervals in pathlets based on these critical points, we restrict the reference curves based on these critical points. Specifically, there are $m=𝒪(n)$ unique $x$-coordinates of points in $Z$, which we order as $x_1,\mathrm{\dots },x_m$. We show that by allowing for pathlets to use subsegments of the reversal $\overleftarrow{e}$ of $e$ as reference curves, we may restrict reference curves to be of the form $e[x_i,x_{i^{\prime }}]$ or $\overleftarrow{e}[x_i,x_{i^{\prime }}]$ to not lose much coverage. That is, the optimal $(2,{\mathrm{\Delta }}^{\prime })$-pathlet with such a reference curve covers at least one-fourth of what any other $(2,{\mathrm{\Delta }}^{\prime })$-pathlet using a subsegment of $e$ as a reference curve covers.

The remainder of our subedge pathlet construction algorithm follows the same procedure as for vertex-to-vertex pathlets, though with the following optimization. We consider every $x_i$ separately, for $i\in [m]$. However, rather than considering all reference curves $e[x_i,x_{i^{\prime }}]$, of which there are $m-i$, we consider only $𝒪(\log (m-i))$ reference curves. The main observation is that we may split a pathlet $(e[x_i,x_{i^{\prime }}],ℐ)$ into two: $(e[x_i,x_{i+2^j}],{ℐ}_1)$ and $(e[x_{i^{\prime }-2^j},x_{i^{\prime }}],{ℐ}_2)$, for some $j\le \log (m-i)$. One of the two pathlets covers at least half of what $(e[x_i,x_{i^{\prime }}],ℐ)$ covers, so an optimal $(2,{\mathrm{\Delta }}^{\prime })$-pathlet $(e[x_i,x_{i+2^j}],ℐ)$ that is defined by critical points covers at least one-eighth of any other subedge $(2,{\mathrm{\Delta }}^{\prime })$-pathlet $(e[x,x^{\prime }],{ℐ}^{\prime })$.

For every $i\in [m]$, we let $Z_i\subseteq Z$ be the subset of critical points with $x$-coordinate equal to $x_i$ or $x_{i+2^j}$ for some $j\le \log (m-i)$. We construct the reachability graph $G(e,T,Z_i)$, which has $𝒪(n{\log }^{2}n)$ complexity. We then proceed as with the vertex-to-vertex pathlets, using a sweepline through the reachability graph. Doing this for all $i$ (and remembering the optimal pathlet) thereby takes $𝒪(n^2{\log }^{3}n)$ total time and $𝒪(n{\log }^{2}n)$ space. Taken over all edges of $S$, we obtain a subedge pathlet in $𝒪(n^3{\log }^{3}n)$ time and $𝒪(n{\log }^{2}n)$ space.

Consider any $(\mathrm{\ell },\mathrm{\Delta })$-pathlet $(P,ℐ)$ and choose some interval $[a,b]\in ℐ$. For all $[c,d]\in ℐ$, via the triangle inequality, $d_F(T[a,b],T[c,d])\le 2\mathrm{\Delta }$. Let $S[s,t]$ be the subcurve of $S$ matched to $T[a,b]$ by $(f,g)$. Naturally, $d_F(S[s,t],T[a,b])\le 2\mathrm{\Delta }$, and so by the triangle inequality $d_F(S[s,t],T[c,d])\le 4\mathrm{\Delta }$. By the definition of a pathlet-preserving simplification, we obtain that for every curve $P^{\prime }$ with $d_F(P^{\prime },T[a,b])\le \mathrm{\Delta }$, we have $|P^{\prime }|\ge |S[s,t]|-2+|\mathbb{N}\cap \{s,t\}|$. In particular, setting $P^{\prime }\leftarrow P$ implies that $|S[s,t]|\le \mathrm{\ell }+2-|\mathbb{N}\cap \{s,t\}|$. Thus $(S[s,t],ℐ)$ is an $(\mathrm{\ell }+2-|\mathbb{N}\cap \{s,t\}|,4\mathrm{\Delta })$-pathlet. $◀$

The curve $S$ that we construct is a curve-restricted $\alpha \mathrm{\Delta }$-simplification of $T$; a curve whose vertices lie on $T$, where for every edge $s=\overline{T(a)T(b)}$ of $S$ we have $d_F(s,T[a,b])\le \alpha \mathrm{\Delta }$. Various $\alpha \mathrm{\Delta }$-simplification algorithms have been proposed [17, 2, 14, 19].

If $T$ is a curve in ${ℝ}^2$, Guibas et al. [17] provide an $𝒪(n\log n)$ time algorithm that constructs a $2\mathrm{\Delta }$-simplification $S$ for which there is no $\mathrm{\Delta }$-simplification $S^{\prime }$ with . Their algorithm is not efficient in higher dimensions however.

Agarwal et al. [2] also construct a $2\mathrm{\Delta }$-simplification $S$ of $T$ in $𝒪(n\log n)$ time. This was applied by Akitaya et al. [3] for their subtrajectory clustering algorithm under the discrete Fréchet distance. The simplification $S$ has a similar guarantee as the simplification of [17]: there exists no vertex-restricted $\mathrm{\Delta }$-simplification $S^{\prime }$ with . This guarantee is weaker than that of [17], as vertex-restricted simplifications are simplifications formed by taking a subsequence of vertices of $T$ as the vertices of the simplification. It can, however, be constructed efficiently in higher dimensions.

As we show in Figure 3, the complexity of a vertex-restricted $\mathrm{\Delta }$-simplification can be arbitrarily bad compared to the (unrestricted) $\mathrm{\Delta }$-simplification with minimum complexity. Brüning et al. [5] note that for the subtrajectory problem under the continuous Fréchet distance, one requires an $\alpha \mathrm{\Delta }$-simplification whose complexity has guarantees with respect to the optimal (unrestricted) simplification. They present a $3\mathrm{\Delta }$-simplification $S$ (whose definition was inspired by de Berg, Gudmundsson and Cook [14]) with the following property: for any subcurve $T[a,b]$ of $T$ within Fréchet distance $\mathrm{\Delta }$ of some line segment, there exists a subcurve $S[s,t]$ of $S$ with complexity at most $4$ that has Fréchet distance at most $3\mathrm{\Delta }$ to $T[a,b]$. Thus, there exists no $\mathrm{\Delta }$-simplification $S^{\prime }$ with .

In Definition 6 we presented yet another curve simplification under the Fréchet distance for curves in ${ℝ}^d$. Our simplification has a stronger property than the one that is realized by Brüning et al. [5]: for any subcurve $T[a,b]$ and any curve $P$ with $d_F(P,T[a,b])\le \mathrm{\Delta }$, we require that there exists a subcurve $S[s,t]$ with $d_F(S[s,t],T[a,b])\le 2\mathrm{\Delta }$ that has at most two more vertices than $P$. This implies both the property of Brüning et al. [5] and ensures that no $\mathrm{\Delta }$-simplification $S^{\prime }$ exists with .

In the full version of our paper we provide an efficient algorithm for constructing pathlet-preserving simplifications. The algorithm is an extension of the vertex-restricted simplification of Agarwal et al. [2] to construct a curve-restricted simplification instead. For this, we use the techniques of Guibas et al. [17] to quickly identify if an edge of $T$ is suitable to place a simplification vertex on. We combine this check with the algorithm of [2] and obtain:

We apply this greedy strategy to subtrajectory clustering, putting the focus on constructing a pathlet that covers the most of some universe $𝒰$. For subtrajectory clustering, the universe is, in principle, infinite. We therefore first define a discrete universe $𝒰$ consisting of $𝒪(n^3)$ intervals that together cover $[1,n]$. We choose this universe carefully, as an optimal covering of $𝒰$ with pathlets must have roughly the same size as an optimal covering of $[1,n]$. We define $𝒰$ using the following set of critical points in ${\mathrm{\Delta }}^{\prime }-\mathrm{FSD}(S,T)$:

Fix an integer $i\in [|S|-1]$. We compute the critical points inside the cells $[i,i+1]\times [j,j+1]$, for all $j\in [n-1]$, in $𝒪(n^2)$ time altogether. For this, we compute the sets $X_{i,j}$ of Definition 9 in $𝒪(1)$ time each. Let $X_i={\bigcup }_j{X}_{i,j}$. Then, we compute the intersections of each vertical line $\{x\}\times [1,n]$, for $x\in X_i$, in $𝒪(n)$ time each. The critical points inside the cells $[i,i+1]\times [j,j+1]$, for $j\in [n-1]$, are the endpoints of connected components of these intersections, and can be computed in $𝒪(n)$ time per line, totalling $𝒪(n^2)$ time. Summing over all integers $i$ completes the proof. $◀$

In the remainder of this paper, we let $𝒰$ denote this discrete universe. For notational convenience, we denote for a pathlet $(P,ℐ)$ by $\mathrm{Cov}(P,ℐ)$ the set ${\mathrm{Cov}}_{𝒰}(P,ℐ)$. We generalize the analysis of the greedy set cover argument to pathlets that cover a (constant) fraction of what the optimal pathlet covers. This relaxes the requirements on the pathlets and helps reduce complexity of the problem. For this, we introduce the following:

In Lemma 13, we show that if we keep greedily selecting $(\mathrm{\Delta },\frac{1}{c})$-maximal pathlets for our clustering, the size of the clustering stays relatively small compared to the optimum size. The bound closely resembles the bound obtained by the argument for greedy set cover.

Let $C^{\ast }={\{(P_i,{ℐ}_i)\}}_{i=1}^k$ be an $(\mathrm{\ell },\mathrm{\Delta })$-clustering of $T$ of minimal size. Then $k:=|C^{\ast }|=k_{\mathrm{\ell }}(\mathrm{\Delta })$. Consider iteration $j$ of the algorithm, where we have some set of $(\mathrm{\ell },{\mathrm{\Delta }}^{\prime })$-pathlets $C_j$. Denote by $W_j=|𝒰|\setminus \mathrm{Cov}(C_j)$ the “size” of the part of the universe that still needs to be covered. Since $C^{\ast }$ covers $𝒰$, it must cover $𝒰\setminus \mathrm{Cov}(C_j)$. It follows via the pigeonhole principle that there is at least one $(\mathrm{\ell },\mathrm{\Delta })$-pathlet $(P_i,{ℐ}_i)\in C^{\ast }$ that covers at least $W_j/k$ intervals in $\mathrm{Cov}(P_i,{ℐ}_i)\setminus \mathrm{Cov}(C_j)$. Per definition of being $(\mathrm{\Delta },\frac{1}{c})$-maximal, our greedy algorithm finds a pathlet $(P_j,{ℐ}_j)$ that covers at least $\frac{W_j}{ck}$ uncovered intervals. Thus:

We have that $W_0=|𝒰|$. Suppose it takes $k^{\prime }+1$ iterations to cover all of $T^{\prime }$ with the greedy algorithm. Then before the last iteration, at least one edge of $T^{\prime }$ remained uncovered. That is, $|𝒰|\cdot {\left(1-\frac{1}{c\cdot k}\right)}^{k^{\prime }}\ge 1$. We apply that $e^x\ge 1+x$ for all real $x$ to obtain:

for all $x\ge 1$. Plugging in $x\leftarrow c\cdot k$, it follows that

Hence $e^{\frac{k^{\prime }}{c\cdot k}}\le |𝒰|-1$, showing that $k^{\prime }\le c\cdot k\ln (|𝒰|-1)$. Thus after $k^{\prime }+1\le c\cdot k_{\mathrm{\ell }}(\mathrm{\Delta })\ln (|𝒰|-1)+1$ iterations, all of $T^{\prime }$, and therefore $T$, is covered. Using that $|𝒰|\le 6n^3$ completes the proof. $◀$

Recall that we fixed some discrete universe $𝒰$ of $𝒪(n^3)$ intervals, and that we denote $\mathrm{Cov}(P,ℐ)={\mathrm{Cov}}_{𝒰}(P,ℐ)$. In each iteration of our greedy algorithm, we select one of two pathlets whose coverage is the maximum over $𝒰\setminus \mathrm{Cov}(C)$, given the current set of picked pathlets $C$. To compare the coverages of pathlets, we make use of binary search trees built on $𝒰$ and $\mathrm{Cov}(C)$:

We make use of a general data structure for storing a set $ℐ$ of $m$ interior-disjoint intervals, such that given a query interval $I$, the number of intervals in $ℐ$ that are fully contained in $I$ can be reported efficiently. For the data structure, we store the (multiset of) endpoints of intervals in $ℐ$ in a balanced binary search tree. The tree uses $𝒪(m)$ space and is constructed in $𝒪(m\log m)$ time.

We report the number of intervals in $ℐ$ contained in a query interval $I$ as follows. An interval $[a,b]\in ℐ$ is contained in $I$ if and only if both $a$ and $b$ are. Furthermore, there are $k^{\prime }\le 2$ intervals in $ℐ$ that $I$ intersects but does not contain. Thus, if $I$ contains $k$ endpoints stored in the binary search tree, then it contains $(k-k^{\prime })/2$ intervals of $ℐ$. We compute $k^{\prime }$ by reporting the intervals of $ℐ$ containing the endpoints of $I$ in $𝒪(\log m)$ time. Computing $k$ and then reporting $(k-k^{\prime })/2$ takes an additional $𝒪(\log m)$ time. Thus we answer a query in $𝒪(\log m)$ time.

We use the above data structure to efficiently compute $|\mathrm{Cov}(P,ℐ)\setminus \mathrm{Cov}(C)|$ for a query pathlet $(P,ℐ)$. For this, we preprocess both $𝒰$ and $\mathrm{Cov}(C)$ into the above data structure. Since $\mathrm{Cov}(C)\subseteq 𝒰$ and $|𝒰|=𝒪(n^3)$, this takes $𝒪(n^3\log n)$ time, and the data structures use $𝒪(n^3)$ space. With the two data structures, we report the values $|{\mathrm{Cov}}_{𝒰}(P,ℐ)\cap 𝒰|$ and $|\mathrm{Cov}(P,ℐ)\cap \mathrm{Cov}(C)|$ in $𝒪(\log n)$ time. We then report

$◀$

Our algorithm iteratively constructs a set $C$ of $𝒪(k_{\mathrm{\ell }}(\mathrm{\Delta })\log n)$ pathlets. Before we start constructing pathlets, we compute the universe $𝒰$ of $𝒪(n^3)$ intervals. This takes $𝒪(n^3)$ time (Lemma 11).

In each iteration, we construct the data structure of Lemma 15 on the universe $𝒰$ and current set of pathlets $C$. This takes $𝒪(n^3\log n)$ time and uses $𝒪(n^3)$ space. Constructing the vertex-to-vertex pathlet then takes $𝒪(n^2\mathrm{\ell }{\log }^{2}n)$ time and uses $𝒪(n\mathrm{\ell }\log n)$ space (Theorem 19). The subedge pathlet takes $𝒪(n^3{\log }^{3}n)$ time and $𝒪(n{\log }^{2}n)$ space to construct (Theorem 21).

To decide which pathlet to use in the clustering, we make further use of the data structure of Lemma 15. All constructed pathlets $(P,ℐ)$ have $|ℐ|\le n$, and so we compute the coverages of the two pathlets in $𝒪(n\log n)$ time. By summing up all complexities, we derive our main theorem: