TY  - INPR
A1  - Demaine, Erik D.
A1  - Fekete, Sándor P.
A1  - Rote, Günter
A1  - Schweer, Nils
A1  - Schymura, Daria
A1  - Zelke, Mariano
T1  - Integer point sets minimizing average pairwise L1 distance: What is the optimal shape of a town?
T2  - Preprint zu: Computational geometry
N2  - An n-town, n[is an element of]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[superscript 7.5]) time. This is also practically useful, as it allows us to compute optimal solutions up to n=80.
KW  - Manhattan distance
KW  - average pairwise distance
KW  - integer points
KW  - dynamic programming
Y1  - 2010
UR  - http://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/25916
UR  - https://nbn-resolving.org/urn:nbn:de:hebis:30:3-259160
UR  - http://hdl.handle.net/1721.1/62244
SN  - 0925-7721
N1  - Terms of Use: Creative Commons Attribution-Noncommercial-Share Alike 3.0
N1  - Special issue of selected papers from the 21st Annual Canadian Conference on Computational Geometry. Citation: Demaine, Erik D. et al. “Integer Point Sets Minimizing Average Pairwise L1 Distance: What Is the Optimal Shape of a Town?” Computational Geometry 44.2 (2011) : 82-94.
VL  - 44
IS  - 2
SP  - 82
EP  - 94
PB  - Elsevier B.V.
CY  - Amsterdam
ER  -