We introduce a new realistic family of curves, which we call
c-packed curves. Interestingly, this family is closed
under simplification, a property that makes it especially useful.
Next, we present the first near linear time approximation algorithm
for the Frechet distance for polygonal c-packed curves
in Rd. The algorithm also works in near linear
time for low-density curves in the plane. In higher dimensions,
one can approximate the Frechet distance of low-density curves
in subquadratic time.