I have a sequence of $n$ integers, $p_k$, with $0\le k<n$.
Is it possible to find the minima of $(j-k)^2+p_j^2,0\le j<n$ for all $k$ in linear time ?
If it can help, this is equivalent to finding the minima of
$$j^2+p_j^2-2jk$$ or simply $$q_j-2jk$$ where $q_j\ge j^2$.
Update:
If I am right, the last formulation corresponds to the search of the lowest tangency points of lines of slope $2k$ to the graph of $q_j$. This problem is in direct relation to the construction of the lower hull of the curve.