An n-town, n@?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 along the axis-parallel street grid, then an n-town has optimal shape if the sum of all pairwise Manhattan distances is minimized. This problem has been studied for cities, i.e., the limiting case of very large n. For cities, it is known that the optimal shape can be described by a differential equation, for which no closed-form solution is known. We show that optimal n-towns can be computed in O(n^7^.^5) time. This is also practically useful, as it allows us to compute optimal solutions up to n=80.
@cite_12: We consider the problem of placing records in a 2-dimensional storage array so that expected distance between consecutive references is minimized. A simple placement heuristic which uses only relative frequency of access for different records is shown to be within an additive constant of optimal when distance is measured by the Euclidean metric. For the rectilinear and maximum metrics, we show that there is no such heuristic. For the special case in which all access probabilities are equal, however, heuristics within an additive constant of optimal do exist, and their implementation requires solution of differential equations for which we give numerical solutions.
@cite_2: If one defines the distance between two points as the Manhattan distance (the sum of the horizontal distance along streets and the vertical distance along avenues) then one can define a city as being optimal if the average distance between pairs of points is a minimum. In this paper a nonlinear differential equation for the boundary curve of such a city is determined. The problem solved here is the continuous version of an optimization problem on how to design efficient allocation algorithms for massively parallel supercomputers. In the language of continuum mechanics, the shape of the optimal city is that taken by a blob of incompressible fluid composed of molecules whose pairwise interactions are described by an attractive potential proportional to the Manhattan distance between the particles.
Motivated by the problem of storing records in a 2-dimensional array, @cite_12 studied strategies that minimize average access time between successive queries; among other results, they described an optimal solution for the continuous version of our problem: What shape of area @math minimizes the average Manhattan distance between two interior points? Independently, @cite_2 solved this problem in the setting of a city, inspiring the subtitle of this paper. The optimal solution is described by a differential equation, and no closed-form solution is known.