We show how to compute in O(n4/3log 1/3n+n2/3k2/3logn) time the distance between k given pairs of vertices of a planar graph G with n vertices. This improves previous results whenever (n/log n)5/6≤k≤n2/log 6n. As an application, we speed up previous algorithms for computing the dilation of geometric planar graphs.
