Before revision:  As an indicator of hardness, 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:  (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)}.