Diameter and radius in the Manhattan metric (Q910716)

A maximum d set inside given rectilinearly bounded set \(R\subset Z^ n\) of lattice points is by definition a set which has \(L^ 1\)-diameter d and the largest number of points possible. A general question, suggested by Erdős, is for what d and general-sized regions R there is a maximum d set which is contained in a ball of radius d/2 and center in R. The second author and Fellows, who found a partial answer to the Erdős question above, conjectured that the answer is always positive if the center of the ball is not required to be a lattice point. The authors provide in the paper under review a partial verification of this conjecture. As an example, they show that if \(d_ j\) is the largest coordinate difference in the \(j^{th}\) component among members of R and if e(R) is the number of even integers among \(d_ j\) then the conjecture is completely resolved.