Integer point sets minimizing average pairwise \(L_{1}\) distance: What is the optimal shape of a town? (Q621921)

The authors study a special case of the task consisting in finding \(n\) sites from a given set of candidate locations, which minimizes the average distance between the sites. In the special case studied in the paper, a group of \(n\) buildings each occupying; a distinct site on a 2-dimensional integer grid is considered. Such group of buildings is called \(n\)-town and different positions of the building form different shapes of the \(n\)-town. The authors propose a procedure, which makes possible to find the optimal shape of the \(n\)-town, i.e. the shape, which minimizes the sum of all pairwise Manhattan distances between the buildings. Computational experience with the proposed method for values of \(n\) up to \(n= 80\) is presented in the concluding part of the paper.