Before revision:  We show that under some conditions the approximation factor achieved by our data structure is optimal in the cell-probe model of computation. Concretely}\left({k\epsilon}}\right) + \mathcal{O}(nm) and has query time in \mathcal{O}}\left(\right) , we show that for any data structure which achieves an approximation factor less than 2 and which supports curves of arclength at most L, uses a word size bounded by \mathcal{O}(L^{1-\epsilon}) for some constant \epsilon>0, and answers the query using only a constant number of probes, the number of words used to store the data structure must be at least L^{\Omega(k)}.
After revision:  Our second data structure achieves a (2+\epsilon) approximation factor, uses space in n\cdot \mathcal{O}\left({k\epsilon}}\right) + \mathcal{O}(nm) and has query time in \mathcal{O}}\left(\right) , we show that for any data structure which achieves an approximation factor less than 2 and which supports curves of arclength at most L, uses a word size bounded by \mathcal{O}(L^{1-\epsilon}) for some constant \epsilon>0, and answers the query using only a constant number of probes, the number of words used to store the data structure must be at least L^{\Omega(k)}.