we consider the problem of finding routes between any pair of sites
that minimize energy consumption and do not use more than some
constant number $k$ of hops.
We relax the exactness requirement and only require approximation scheme which allows us to guarantee constant query time using linear space and $O(n\log n)$ preprocessing time.
One tool used might be of independent interest:
For any pair of points $(p,q)$
report in constant time the cluster pair $(A,B)$ representing $(p,q)$
in a well-separated pair decomposition of $P$.