In this lesson, we examine the trackless work functions where P is Integer Distances Bounded by N.

In the example illustrated below, N=5. In the diagram above, N=5, and d=rs=2.

Each cell in the matrix (usually white background, but also including red, green, or yellow background) is a point of D, and represents a set of points in M. If the cell is blank, that is the empty set. If the coordinates of a cell are (x,y), that means that the cell represents all points which are distance x from r and distance y from s.

Note that, for any cell which is blank (darker background, and no number) it is possible, using the triangle inequality, to prove that that cell must be empty. We assume that M is P universal, which implies that that no cell is empty unless it is must be empty.

The numbers inside the cells are the values of the trackless work function, which has domain D. The work function itself has domain M. If w is the work function and tau is the trackless work function, and if q in M, then P(q) is in D. Then tau(P(q)) <= w(q).

We can compute the values of the trackless work function, given the information that we are allowed to have. However, we cannot compute the work function, a function on M.

Exercise 3.1. We say a function on M is valid if it could be the work function, given the history of requests. Prove that there exists a valid function w on M such that tau(x,y) = min{w(q)}, where q ranges over all points in M such that P(q) = (x,y). Answer

The trackless work function shown is supported by two of the entries in the table, namely the entry 1 at (1,3), and the entry 0 at (3,2).

Exercise 3.2: Using the naming convention described in Lesson II, verify that the name of this trackless work function is as given in the caption.

Exercise 3.3: The diagram may also be considered to be a subset of the Manhattan (sum norm) plane. When we draw the streets and avenues of Manhattan onto our diagram, what angle(s) would they subtend with the cell boundary lines? Answer

Exercise 3.4: Click on the cell in the diagram which is the image of r.

Exercise 3.5: Click on the cell in the diagram which is the image of s.

Exercise 3.6: We know that M must have a valid function w and a point u where w(u) = 0. Click on the cell in the diagram which is the image of u.

Exercis 3.7: Let v be a point in M which maps to (1,3). What is the distance between u and v? Answer