In this paper a method of minimal neighborhood for cost optimal trajectory planning along prescribed paths is introduced. The method exploits the phase-plane approach. In the phase-plane, in an iterative procedure, subareas of search are built, called neighborings, which surround the current-best trajectory. In each iteration, in order to find the next-best trajectory, the dynamic programming (pruned to the subarea) is used. The method of minimal neighborhood makes the neighborings as small as possible and therefore speeds up computations maximally. The tests carried out on a model of the IRb-6 ASEA robot have shown that the method of minimal neighborhood is much faster than dynamic programming applied to the whole phase-plane, while preserving the quality of the resulting trajectory.