The algorithm may as well assume that M is a universal space. If the algorithm remembers everything it can, it knows that the true workfunction w lies within some set of possible workfunctions, say W = {w_1, w_2, ... }

After t steps, the algorithm's knowledge of the past consists of a partial distance function on pair of points drawn from the set R = {s(0), r(0), r(1), .... r(t)}. That is the set of all points on which the algorithm has had servers. That set has C(t+1,2) = (t^2+t)/2 pairs, but the algorithm knows only 2t distances.

The requests are made in some big space M, but the only points of M that the algorithm has any knowledge about are the points in R. The algorithm considers R to be a subspace of M, which is a metric space in its own right.

For the algorithm to 'know' R as a metric space, it must have its table of distances, which has (t^2+t)/2 entries (not counting those which must be zero) since R has t+1 points. At each step, the algorithm is given two distances. Therefore, can only fill in 2t entries of the table. If t > 1, the table is thus incomplete.

What the algorithm does is to guess the other entries. The known entries, together with the triangle inequality, constrain the possible values of the unknown entries. And, if all distances must be integers, there are only finitely many possible ways to guess the unknown entries.

Exercise: Prove that, if i < j, the distance between r_i and r_j cannot exceed r_i r_{i+1} + ... + r_{j-1} r_j.

After filling in the table, the algorithm now has a metric on R, which call the hypothetical metric. Using the hypothetical metric, and using dynamic programming, it computes a workfunction, which we call the hypotheical workfunction, on R.

Using the hypothetical metric, each point in R projects to some cell of the diagram. That projection is neither one-to-one nor onto, in general. Let us say that r_i in R projects to cell(x_i,y_i), and let w(r_i) be the value of the hypotheical workfunction on that point.

For each cell(x,y) let f(x,y) = min{f(r_i) + max{|x-x_i|,|y-y_i|}}

where the minimum is taken over all r_i in R. (We can allow s_0 = r_{-1}.) Thus, f is 1-Lipschitz. We call f the hypothetical trackless workfunction.

The actual trackless workfunction is defined to be the pointwise minimum of all hypothetical trackless workfunctions.

Thus, the following computation can be used to compute the trackless work function, provided all distances are integers:

1. Loop
2. Choose a metric on R consistent with the algorithm's knowledge
3. Using that metric, compute the values of the workfunction on R
4. Project those values to the cells of the diagram.
5. If all possible metrics have been chosen Exit
6. End Loop
7. For each cell, pick the minimum of all the projected values. (Default value is infinity)
8. For any cell(x,y), define f(x,y) to be the minimum of the quantity value(e,f) + max{|x-e|,|y-f|}, minimized over all choices of cell(e,f) which got a value in the previous step.