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.

  PostScript file (gzipped)   pdf file (gzipped)

Python programs

Numeric results

other papers about this subject
Last update: April 13, 2010.