Mandatory: Approximate Data Structures
Philip Bille Inge Li Gørtz Eva Rotenberg
1 Exercise Consider the following 4 points in R: w = 0, x = 10, y = 20, z =
30. Consider the metric given by distance between the points, eg. d(z, x) =
30− 10 = 20.
In this exercise, you will analyse the performance of Thorup and Zwick’s
distance oracle [1], when run on this particular metric space on 4 points.
For k = 2, run the algorithm preprok from Figure 2 [1] that constructs the
distance oracle.
Assume that the sample is non-empty: if it is empty we will re-run the
algorithm.
The outcome of the sampling is a non-empty subset of {w, x, y, z}. How
many different outcomes are there?
When choosing pi in preprok, assume that ties are broken in favour of
choosing the lexicographically smaller.
Compute the expected value of dist(y, x), the estimated distance between y
and x, according to the algorithm in Figure 2 [1].
Definition In a weighted directed complete graph, there are edges between any
pair of vertices u, v, but the weight of (u, v) may be different from the weight
of (v, u).
2 Exercise. Consider applying the algorithms of Figures 1 and 2 from Tho-
rup and Zwick’s paper [1] to a weighted directed complete graph. Consider the
case where k = 2.
Give an example, preferably a minimal example, of a weighted directed com-
plete graph where the expected output returned by distk differs from the true
distance by more than a factor 3.
That is, calculate the expected value of the estimated distance returned by
the algorithm and compare this number to the actual distance.
3 Exercise. For a weighted directed complete graph as above, is the esti-
mated distance distk returned by the algorithm always larger than or equal to
the actual distance?
Substantiate your answer by providing an argument or a counterexample.
[1] Approximate distance oracles, M. Thorup, U. Zwick, J. ACM, 2005.
1