Given the current position of n sites in a radio network, we discuss the problem of finding routes between pairs of sites such that the energy consumption for this communication is minimized. Though this can be done using Dijkstra’s algorithm on the complete graph in quadratic time, it is less clear how to do it in near linear time. We present such algorithms for the important case where the transmission cost between two sites is the square of their Euclidean distance plus a constant offset. We give an $$ \mathcal{O}\left( {kn log n} \right) $$ time algorithm that finds an optimal path with at most k hops, and an $$ \mathcal{O}\left( {n^{1 + \varepsilon } } \right) $$ time algorithm for the case of an unrestricted number of hops. The algorithms are based on geometric data structures ranging from simple 2-dimensional Delau-nay triangulations to more sophisticated proximity data structures that exploit the special structure of the problem.