In this article :
Kinodynamic Motion Planning
B. Donald, P. Xavier, J. Canny, J. Reif
https://www.cs.duke.edu/brd/papers/src-papers/jacm-final.pdf
The authors present a PTAS algorithm that can compute a safe, close to optimal trajectory from a point A (having a certain speed vector) to a point B (having a certain speed vector). They do this by transforming the problem to finding the shortest path in a directed graph. All vertices in the resulting directed graph have an outgoing degree of 3.
I don't understand how we can find the shortest path in this directed path from one point to another (by using BFS) without the complexity being exponential, since doing a BFS from the starting point until we encounter the end point would take $O(3^x)$ with $x$ being the layer of the BFS.
Instead the complexity that is noted on page 5 of the article is this :
$O( n( \frac{lv\gamma³}{\epsilon⁶})^d)$
$n$ being the number of bounding halfplanes on obstacles, $l$ being the length of the side of a cube in which all points are placed, $v$ is maximum velocity and $\gamma$ is maximum acceleration divided by maximum velocity. $\epsilon$ as always is the approximation value and $d$ the number of dimensions in which our problem is placed. For simplicity let $d$ be $1$.
Clearly we can see this complexity is not exponential, my question is why? Even in one dimension, we still obtain a graph in 2 dimensions (1 for position and one for velocity) and the BFS will still take exponential running time. Am I missing something?
Thanks
