**Reference**:- Erik D. Demaine, Sándor P. Fekete, Günter Rote, Nils Schweer, Daria Schymura, and Mariano Zelke, “Integer Point Sets Minimizing Average Pairwise ℓ
_{1}Distance: What is the Optimal Shape of a Town?”, in*Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG 2009)*, Vancouver, British Columbia, Canada, August 17–19, 2009, pages 145–148. **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*. The optimal shape can be described by a differential equation. No closed-form solution is known. We show that optimal*n*-towns can be computed in time polynomial in*n*. **Length**:- The paper is 4 pages.
**Availability**:- The paper is available in PostScript (559k), gzipped PostScript (209k), and PDF (179k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- MinAvgDistance_CGTA (Integer Point Sets Minimizing Average Pairwise
*L*_{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 13, 2019 by Erik Demaine.