  Using characteristics to treat advection terms in time-dependent PDEs leads
to a class of schemes, e.g., semi-Lagrangian and Lagrange-Galerkin schemes,
which preserve stability under large Courant numbers, and may therefore be
appealing in many practical situations. Unfortunately, the need of locating the
feet of characteristics may cause a serious drop of efficiency in the case of
unstructured space grids, and thus prevent the use of large time-step schemes
on complex geometries. In this paper, we perform an in-depth analysis of the
main recipes available for characteristic location, and propose a technique to
improve the efficiency of this phase, using additional information related to
the advecting vector field. This results in a clear improvement of execution
times in the unstructured case, thus extending the range of applicability of
large time-step schemes.
