The total computational cost \(C_t\)  of algorithm FSS is the sum of the cost \(C_k\) 
of computing the approximation \(W^k\)  of the affinity matrix \(W\)  plus the cost \(C_s\)  of clustering the rows of \(W^k\)  in \(n_c\)  clusters.
If \(m\)  is the cost of computing the distance \(d\)  between two faces of a given triangulation with \(n\)  faces (this cost strongly
depends of the underlying metric, for instance if the metric is the geodesic or the angular metric, then \(m=O(n \log (n))\)  ), then
\(C_k=O(knm)\) . Since \(k\) , \(n_c\)  and the number \(n_i\)  of Lloyd [1]} iterations are bounded,
it holds that \(C_s=O(n_in_ckn)\) . Thus, if only \(k << n\)  columns of the affinity matrix \(W\)  are computed,
then the total cost \(C_t\)  is dominated by \(C_k\) , i.e., \(C_t=O(nm)\) .
In the numerical experiments of the next section we show that the immersion based on the farthest triangle provides a good
approximation of \(W\)  and therefore it is useful to perform the segmentation.
