I am feeling hopeful and confused at the same time here
It seems that there are pitfalls, but there is light at the end. Given an accuracy requirement of "good enough", how can it be done?
There are a bunch of ways ... given arbitrary prediction function c(t), the simplest/dumbest method is probably to just brute force test a bunch of values of t and see if "||(c(t)-p)||^2 = (s*t)^2" is close to true for any of them. The next method after that is probably the bisection method Jasmine mentioned, which is a binary search for the intersection:
http://en.wikipedia.org/wiki/Bisection_methodTo do bisection first just rearrange the test equation like so:
||(c(t)-p)||^2 - (s*t)^2 = 0
And call that left hand side f(t)
Now just search for some t_i where f(t_i)>0 and some t_f where f(t_f)<0. If you find those, do a binary search between the two times to find when f(t) ~= 0
If you fail to find any time t_f where f(t_f) < 0, assume there's no intersection.
To do binary search, just iteratively compute the midpoint t_m=.5*(t_f+t_i), and then if f(t_m) < 0 it replaces t_f, else it replaces t_i.