A competitive strategy for distance-aware online shape allocation
A competitive strategy for distance-aware online shape allocation
复制标题
距离感知在线形状分配的竞争策略
DOI：
10.1016/j.tcs.2014.02.050
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
N. Schweer
中科院分区：
文献类型：
--
作者：
S.P. Fekete;J.-M. Reinhardt;N. Schweer
考虑如下在线分配问题：给定一个单位正方形S和一个数列ni ∈[0，1]，其中∑ j= 0 i n j <$1;在每一步i，选择一个区域Ci，该区域Ci是S中先前未分配的区域ni.目标是使这些区域在距离感知意义上紧凑：最小化来自同一集合Ci的点之间的最大（归一化）平均曼哈顿距离。相关的选址问题已经得到了相当多的关注;特别是，确定“城市的最佳形状”的问题，即分配一个单一的n i已经研究。我们提出了一个在线策略，基于空间填充曲线的分析，对于连续形状，我们证明了一个因子为1.8092，离散点集为1.7848。
We consider the following online allocation problem: Given a unit square S, and a sequence of numbers n i∈[0, 1] with∑ j= 0 i n j⩽ 1; at each step i, select a region C i of previously unassigned area n i in S. The objective is to make these regions compact in a distance-aware sense: minimize the maximum (normalized) average Manhattan distance between points from the same set C i. Related location problems have received a considerable amount of attention; in particular, the problem of determining the “optimal shape of a city”, ie, allocating a single n i has been studied. We present an online strategy, based on an analysis of space-filling curves; for continuous shapes, we prove a factor of 1.8092, and 1.7848 for discrete point sets.
登录
查看更多内容
DOI：
10.1109/icpr.1994.577130
发表时间：
1994-10
期刊：
Proceedings of the 12th IAPR International Conference on Pattern Recognition, Vol. 2 - Conference B: Computer Vision & Image Processing. (Cat. No.94CH3440-5)
影响因子：
--
作者：
C. Gotsman;M. Lindenbaum
通讯作者：
C. Gotsman;M. Lindenbaum
空间填充曲线和无限图
DOI：
10.1007/bfb0000120
发表时间：
1982
期刊：
ArXiv
影响因子：
--
作者：
R. Siromoney;K. Subramanian
通讯作者：
K. Subramanian
图语法及其在计算机科学中的应用
影响因子：
4.4
作者：
H. Ehrig;M. Nagl;G. Rozenberg
通讯作者：
G. Rozenberg
整数点集最小化平均成对 l1 距离：城镇的最佳形状是什么？
DOI：
10.1016/j.comgeo.2010.09.004
发表时间：
2010
期刊：
Proceedings. IEEE International Conference on Cluster Computing
影响因子：
--
作者：
E. Demaine;S. Fekete;G. Rote;Nils Schweer;Daria Schymura;Mariano Zelke
通讯作者：
Mariano Zelke
紧凑位置问题
DOI：
10.1016/s0304-3975(96)00304-0
发表时间：
1993
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
S. O. Krumke;M. Marathe;H. Noltemeier;V. Radhakrishnan;S. Ravi;D. Rosenkrantz
通讯作者：
D. Rosenkrantz