login
A193452
Optimal towns for n>=1.
1
0, 1, 4, 8, 16, 25, 38, 54, 72, 96, 124, 152, 188, 227, 272, 318, 374, 433, 496, 563, 632, 716, 804, 895, 992, 1091, 1204, 1318, 1442, 1570, 1704, 1840, 1996, 2153, 2318, 2486, 2656, 2847, 3040, 3241, 3446, 3662, 3886, 4112, 4360, 4612, 4868, 5128, 5398
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
Cf. A290190.
Sequence in context: A369566 A022560 A290190 * A003451 A277029 A013934
KEYWORD
nonn
AUTHOR
Ctibor O. Zizka, Jul 26 2011
STATUS
approved