OFFSET
1,3
COMMENTS
An n-town, n an integer, 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 along the axis-parallel street grid, then an n-town has optimal shape if the sum of all pairwise Manhattan distances is minimized. (Data for this sequence are from Table 1, page 18, see reference link.)
LINKS
Erik D. Demaine, Sandor P. Fekete, Guenter Rote, Nils Schweer, Daria Schymura, Mariano Zelke, Integer Point Sets Minimizing Average Pairwise L1-Distance: What is the Optimal Shape of a Town?, arXiv:1009.5628 [cs.CG], 2010.
R. M. Karp, A. C. McKellar, C. K. Wong, Near-Optimal Solutions to a 2-Dimensional Placement Problem, SIAM J. Comput., 4(3), 271-286.
CROSSREFS
KEYWORD
nonn
AUTHOR
Ctibor O. Zizka, Jul 26 2011
STATUS
approved