Erik D. Demaine, Sándor P. Fekete, Günter Rote, Nils Schweer,
Daria Schymura, and Mariano Zelke:
1. Integer point sets minimizing average pairwise l1 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 L1 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(n7.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.