Paper by Erik D. Demaine

Reference:

Carl M. Bender, Michael A. Bender, Erik D. Demaine, and Sándor P. Fekete, “What is the optimal shape of a city?”, Journal of Physics A: Mathematical and General, volume 37, number 1, January 2004, pages 147–159.

Abstract:

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.

Length:

The paper is 13 pages.

Availability:

The paper is available in PDF (169k).

See information on file formats.

[Google Scholar search]

Related papers:

MinAvgDistance_CCCG2009 (Integer Point Sets Minimizing Average Pairwise ℓ₁ Distance: What is the Optimal Shape of a Town?)

MinAvgDistance_Algorithmica (Communication-Aware Processor Allocation for Supercomputers)

MinAvgDistance_WADS2005 (Communication-Aware Processor Allocation for Supercomputers)