论文标题
竞争地点问题：平衡设施位置和单轮曼哈顿Voronoi游戏
Competitive Location Problems: Balanced Facility Location and the One-Round Manhattan Voronoi Game
论文作者
论文摘要
我们在连续的环境中研究竞争地点问题，其中必须将设施放置在矩形域$ r $的归一化尺寸为$ 1 $和$ρ\ geq 1 $的范围内，并且根据曼哈顿度量标准来测量距离。我们表明，“平衡”设施配置的家族（在该度量相对于许多几何特性相对于单个设施的Voronoi细胞均等）在该度量中比欧几里得距离要丰富。我们的主要结果考虑了曼哈顿距离的“单轮Voronoi游戏”，其中首先是White，然后玩家Black每个位置$ n $ n $ n $ in $ r $;每个玩家都会为其一个设施之一比对手的设施更近的区域得分。我们给出一个紧密的特征：当且仅当$ρ\ geq n $时，怀特就有一个获胜的策略；对于所有其他情况，我们提出了黑色的获胜策略。
We study competitive location problems in a continuous setting, in which facilities have to be placed in a rectangular domain $R$ of normalized dimensions of $1$ and $ρ\geq 1$, and distances are measured according to the Manhattan metric. We show that the family of 'balanced' facility configurations (in which the Voronoi cells of individual facilities are equalized with respect to a number of geometric properties) is considerably richer in this metric than for Euclidean distances. Our main result considers the 'One-Round Voronoi Game' with Manhattan distances, in which first player White and then player Black each place $n$ points in $R$; each player scores the area for which one of its facilities is closer than the facilities of the opponent. We give a tight characterization: White has a winning strategy if and only if $ρ\geq n$; for all other cases, we present a winning strategy for Black.
