Integer Point Sets Minimizing Average Pairwise l1 Distance: What is the Optimal Shape of a Town?
Integer Point Sets Minimizing Average Pairwise l1 Distance: What is the Optimal Shape of a Town?
复制标题
整数点集最小化平均成对 l1 距离：城镇的最佳形状是什么？
DOI：
10.1016/j.comgeo.2010.09.004
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Mariano Zelke
中科院分区：
文献类型：
--
作者：
E. Demaine;S. Fekete;G. Rote;Nils Schweer;Daria Schymura;Mariano Zelke
一个n-城镇，n∈N，是一组n个建筑物，每个建筑物在一个二维整数网格上占据一个不同的位置。如果我们测量两个建筑物之间的距离沿着轴平行的街道网格，然后一个n-镇具有最佳形状，如果所有成对的曼哈顿距离之和最小化。这个问题已经研究了城市，即，极大n的极限情况。对于城市，已知最佳形状可以由微分方程描述，对于该微分方程没有已知的封闭形式的解。我们证明了最优的n-城镇可以在O（n7.5）时间内计算。这在实际中也很有用，因为它允许我们计算n=80的最优解。
An n-town, n∈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.