Competitive location problems: balanced facility location and the One-Round Manhattan Voronoi Game
研究了在矩形区域内按曼哈顿距离度量时，设施配置的平衡性质，并完整刻画了单轮沃罗诺伊博弈中先手白方获胜的条件（当且仅当矩形长宽比≥设施数）。
Abstract 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 $$\rho \ge 1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ρ</mml:mi> <mml:mo>≥</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> , 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 $$\rho \ge n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ρ</mml:mi> <mml:mo>≥</mml:mo> <mml:mi>n</mml:mi> </mml:mrow> </mml:math> ; for all other cases, we present a winning strategy for Black.