Integer Point Sets Minimizing Average Pairwise L1-Distance: What is the Optimal Shape of a Town?

Erik D. Demaine, Sandor P. Fekete, Guenter Rote +3

An n-town, for a natural number n, is a group of n buildings, each occupying a distinct position on a 2-dimensional integer grid. If we measure the distance between two buildings a…