Paper by Erik D. Demaine
- 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.
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
- The paper is 4 pages.
- 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 L1 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.
These pages are generated automagically from a
Last updated June 1, 2023 by