  Time Optimal Path Parametrization is the problem of minimizing the time
interval during which an actuation constrained agent can traverse a given path.
Recently, an efficient linear-time algorithm for solving this problem was
proposed. However, its optimality was proved for only a strict subclass of
problems solved optimally by more computationally intensive approaches based on
convex programming. In this paper, we prove that the same linear-time algorithm
is asymptotically optimal for all problems solved optimally by convex
optimization approaches. We also characterize the optimum of the Time Optimal
Path Parametrization Problem, which may be of independent interest.
