**Reference**:- Erik D. Demaine, Sándor P. Fekete, Günter Rote, Nils Schweer, Daria Schymura, and Mariano Zelke, “Integer Point Sets Minimizing Average Pairwise
*L*_{1}Distance: What is the Optimal Shape of a Town?”,*Computational Geometry: Theory and Applications*, volume 44, number 2, February 2011, pages 82–94. **Abstract**:-
An
*n-town*,*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. **Comments**:- This paper is also available from ScienceDirect.
**Length**:- The paper is 26 pages.
**Availability**:- The paper is available in PostScript (834k), gzipped PostScript (323k), and PDF (294k).
- 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_JPhysA (What is the optimal shape of a city?)

See also other papers by Erik Demaine.

Last updated September 18, 2020 by Erik Demaine.