Paper by Erik D. Demaine

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₁ 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 ℓ₁ 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?)