  Given an affine algebra $R=K[x_1,\dots,x_n]/I$ over a field $K$, where $I$ is
an ideal in the polynomial ring $P=K[x_1,\dots,x_n]$, we examine the task of
effectively calculating re-embeddings of $I$, i.e., of presentations $R=P'/I'$
such that $P'=K[y_1,\dots,y_m]$ has fewer indeterminates. For cases when the
number of indeterminates $n$ is large and Gr\"obner basis computations are
infeasible, we have previously introduced the method of $Z$-separating
re-embeddings. This method tries to detect polynomials of a special shape in
$I$ which allow us to eliminate the indeterminates in the tuple $Z$ by a simple
substitution process. Here we improve this approach by showing that suitable
candidate tuples $Z$ can be found using the Gr\"obner fan of the linear part of
$I$. Then we describe a method to compute the Gr\"obner fan of a linear ideal,
and we improve this computation in the case of binomial linear ideals using a
cotangent equivalence relation. Finally, we apply the improved technique in the
case of the defining ideals of border basis schemes.
