  Suppose that $S$ is a surface of positive complexity and $N \subset S$ is a
tie neighbourhood of a large train track $\tau$ in $S$. Suppose that $\alpha$
is a properly immersed, essential, and non-peripheral arc or curve in $S$. We
present a polynomial-time algorithm that, given $S$, $N$, and $\alpha$,
homotopes $\alpha$ into efficient position with respect to $N$.
  Proofs for the existence of efficient position were previously given in
[Takarajima,2000] and [MasurMosherSchleimer,2012]. In [Takarajima,2000], a
constructive proof for the existence of efficient position is given for
immersed curves on closed surfaces of genus greater than or equal to two. There
is no discussion of the complexity of the implied algorithm. In
[MasurMosherSchleimer,2012], the existence of efficient position is proved for
embedded curves with respect to birecurrent train tracks on surfaces of
positive complexity. The implied algorithm operates via an exhaustive search.
No time bounds can be deduced.
  We note that the algorithm presented in this thesis and the algorithm
suggested by a careful reading of [Takarajima,2000] coincide in the case of
closed surfaces. However, this thesis constitutes more than a time-complexity
analysis of Takarajima's constructive proof. Firstly, we are more general as we
allow surfaces with boundary, whereas Takarajima only considers closed
surfaces. Secondly, our combinatorial set-up uses arcs and curves with
transverse self-intersection, whereas the barycentric subdivision of
complementary regions carried out in [Takarajima,2000] forces non-transverse
self-intersection even for curves which are initially embedded. Thirdly, the
algorithm in this thesis is formulated purely in terms of local homotopies,
whereas [Takarajima,2000] requires semi-local arguments. Thus, we can, and do,
give pseudocode for our algorithm as well as prove its correctness.
