  We introduce a new numerical method to approximate the solution of a finite
horizon deterministic optimal control problem. We exploit two
Hamilton-Jacobi-Bellman PDE, arising by considering the dynamics in forward and
backward time. This allows us to compute a neighborhood of the set of optimal
trajectories, in order to reduce the search space. The solutions of both PDE
are successively approximated by max-plus linear combinations of appropriate
basis functions, using a hierarchy of finer and finer grids. We show that the
sequence of approximate value functions obtained in this way does converge to
the viscosity solution of the HJB equation in a neighborhood of optimal
trajectories. Then, under certain regularity assumptions, we show that the
number of arithmetic operations needed to compute an approximate optimal
solution of a $d$-dimensional problem, up to a precision $\varepsilon$, is
bounded by $O(C^d (1/\varepsilon) )$, for some constant $C>1$, whereas ordinary
grid-based methods have a complexity in$O(1/\varepsilon^{ad}$) for some
constant $a>0$.
