Distance estimation and object location via rings of neighbors

We consider four problems on distance estimation and object location which share the commonflavor of capturing global information via informative node labels: low-stretch routing schemes [47], distance labeling [24], searchable small worlds [30], and triangulation-based distance estimation [33]. Focusing on metrics of low doubling dimension, we approach these problems with a common technique called rings of neighbors, which refers to a sparse distributed data structure that underlies all our constructions. Apart from improving the previously known bounds for these problems, our contributions include extending Kleinberg’s small world model to doubling metrics, and a short proof of the main result in Chan et al. [14]. Doubling dimension is a notion of dimensionality for general metrics that has recently become a useful algorithmic concept in the theoretical computer science literature.