I'm interested in understanding some recent theoretical results on pathfinding. Specifically this paper:
I understand from the paper that in certain types of graphs (road networks for example) a small set of nodes are sufficient to cover a large number of shortest paths. I also understand that the size of the hitting set that forms such a cover can differ from node to node but is upper bounded by some integer h which is called the highway dimension of the graph.
i) The concept of highway dimension is defined in this paper (Defi 3.4, page 5) using a distance parameter r and a hitting set H which exists for every vertex v in the graph. Specifically, the authors say (slightly paraphrasing) "for all r > 0 and all v there exists a H whose size is bounded by h (the highway dimension of the graph)"
I don't know how to interpret this: is the highway-dimension h constant for all tuples (r, v) or does the value depend on the choice of r? I tend toward the former interpretation but the paper seems ambiguous on this point.
ii) The definition also makes reference to paths P of length > r which can be reached from the vertex v with distance no more than 2r. I don't understand the significance of the (r, 2r) construction. Would it not be simpler to construct a hitting set that covers all paths which begin at v and have length > r? What is gained by this more complicated definition?