Summary: A critical step in a cutting plane algorithm is separation, i.e., establishing whether a given vector \(x\) violates an inequality belonging to a specific class. It is customary to express the time complexity of a separation algorithm in the number of variables \(n\). Here, we argue that a separation algorithm may instead process the vector containing the positive components of \(x\), denoted as \(supp (x)\), which offers a more compact representation, especially if \(x\) is sparse; we also propose to express the time complexity in terms of \(|\mathrm{supp} (x)|\). Although several well-known separation algorithms exploit the sparsity of \(x\), we revisit this idea in order to take sparsity explicitly into account in the time-complexity of separation and also design faster algorithms. We apply this approach to two classes of facet-defining inequalities for the three-index assignment problem, and obtain separation algorithms whose time complexity is linear in \(|\mathrm{supp} (x)|\) instead of \(n\). We indicate that this can be generalized to the axial \(k\)-index assignment problem and we show empirically how the separation algorithms exploiting sparsity improve on existing ones by running them on the largest instances reported in the literature.