Before revision:  Our algorithm runs in O(kn^2), where k depends on \epsilon and the ratio of the duration of  trajectory to the maximum amount of gap time.
After revision:  Our algorithm runs in O(kn^2), where k depends on \epsilon and the ratio of the duration of the trajectory to the maximum amount of gap time.