Before revision:  Our approach consists of a discretization of space based on the input curves, which allows us to prepare a small set of curves that captures all possible queries approximately. Our method is simple and deterministic, yet, somewhat surprisingly, it is more efficient than all previous methods. We also apply our method to a version of approximate range counting for curves and achieve similar bounds.
After revision:  Our method is simple to implement, deterministic, and results in an exponential improvement in both query time and storage space compared with all previous work. Further, we also consider the asymmetric version of ANNC, where the length of the query curves is k \ll m, and obtain essentially the same storage and query bounds as above, except that m is replaced by k. Finally, we apply our method to a version of approximate range counting for curves and achieve similar bounds.