Counting Sets of Lattice Points in the Plane with a Given Diameter under the Manhattan and Chebyshev Distances

Abstract

In this paper, we present new algorithms for counting the sets of lattice points in the plane whose diameter is a given value D, under the Manhattan (L1) and Chebyshev (L infinity) distances. We consider two versions of the problem: counting all sets within a given lattice U times V, and counting all sets that are not equivalent under translations.