A193452 - OEIS

%I #26 Aug 16 2017 04:31:50

%S 0,1,4,8,16,25,38,54,72,96,124,152,188,227,272,318,374,433,496,563,

%T 632,716,804,895,992,1091,1204,1318,1442,1570,1704,1840,1996,2153,

%U 2318,2486,2656,2847,3040,3241,3446,3662,3886,4112,4360,4612,4868,5128,5398

%N Optimal towns for n>=1.

%C 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.)

%H Erik D. Demaine, Sandor P. Fekete, Guenter Rote, Nils Schweer, Daria Schymura, Mariano Zelke, <a href="http://arxiv.org/abs/1009.5628">Integer Point Sets Minimizing Average Pairwise L1-Distance: What is the Optimal Shape of a Town?</a>, arXiv:1009.5628 [cs.CG], 2010.

%H R. M. Karp, A. C. McKellar, C. K. Wong, <a href="https://doi.org/10.1137/0204023">Near-Optimal Solutions to a 2-Dimensional Placement Problem,</a> SIAM J. Comput., 4(3), 271-286.

%Y Cf. A290190.

%K nonn

%O 1,3

%A _Ctibor O. Zizka_, Jul 26 2011