Diameter and radius in the Manhattan metric (Q910716): Difference between revisions
From MaRDI portal
Removed claims |
Changed an Item |
||
Property / author | |||
Property / author: Daniel J. Kleitman / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Rade T. Živaljević / rank | |||
Normal rank |
Revision as of 22:21, 10 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Diameter and radius in the Manhattan metric |
scientific article |
Statements
Diameter and radius in the Manhattan metric (English)
0 references
1990
0 references
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.
0 references
maximum d set
0 references