Paper by Erik D. Demaine
- 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.
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.
- The paper is 13 pages.
- 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 ℓ1 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)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated November 19, 2021 by