## Erik D. Demaine, Sándor P. Fekete, Günter Rote, Nils Schweer,
Daria Schymura, and Mariano Zelke:

# 1. Integer point sets minimizing average pairwise `l`_{1} distance: What
is the optimal shape of a town?

*In: Proceedings of the 21st Annual Canadian Conference on Computational
Geometry, Vancouver, August 17–19, 2009, pp. 145–148.
*
# 2. Integer point sets minimizing average pairwise `L`_{1} distance: What
is the optimal shape of a town?

*Computational Geometry, Theory and Applications* **44** (2011),
82–94. (Special issue for the 21st Canadian Conference
on Computational Geometry, Vancouver, 2009) doi:10.1016/j.comgeo.2010.09.004
### Abstract

An `n`-town, for a natural number `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.
### Python programs

### Numeric results

Last update: April 13, 2010.