We adapt and generalize a heuristic for $k$-center clustering to the permutation case, where every prefix of the ordering is a guaranteed approximate solution. The one-hop greedy permutations work by choosing at each step the farthest unchosen point and then looking in its local neighborhood for a point that covers the most points at a certain scale. This balances the competing demands of reducing the coverage radius and also covering as many points as possible. This idea first appeared in the work of Garcia-Diaz et al. and their algorithm required $O(n^2\log n)$ time for a fixed $k$ (i.e.\ not the whole permutation). We show how to use geometric data structures to approximate the entire permutation in $O(n \log \Delta)$ time for metrics sets with spread $\Delta$. Notably, this running time is asymptotically the same as the running time for computing the ordinary greedy permutation.

@inproceedings{sheehy20onehop,
  title = {One Hop Greedy Permutations},
  author = {Donald R. Sheehy},
  booktitle = {Proceedings of the 32nd Canadian Conference on Computational Geometry},
  pages = {221--225},
  year = {2020}}