On the facility location problem: One-round weighted Voronoi game

Paper pages (47-56)

Introduction

The Voronoi game is a simple geometric model for competitive facility location problem which is played by two players, White and Black, in a continuous space (one-dimensional or two-dimensional). In the one-round game, White places all his n points. After that, Black places the same number of points on the game space. The players Cannot change or reuse a point that was placed before. At the end of the game, the Voronoi diagram of all 2n points is constructed and a player who obtains the larger total area is the winner.

Ahn et al. considered the Voronoi game on a unit circle and a line. They presented a winning strategy for the second player and showed that the first player can preserve the winning margin as small as possible. Cheong et al. presented a winning strategy for the second player when

on a square. Fekete et al. considered the two-dimensional version of Voronoi game on a rectangular area of aspect ratio ρ. They showed that there is a winning strategy for the second player where with and for with and the first player wins in the other situations. Rashid et al. introduced a new version of Voronoi game called neighbor Voronoi and presented the winning strategies based on the neighborhood of points. Bandyapadhyay et al. studied Voronoi game on a weighted graph and showed that the problem of finding a winning strategy for the second player is NP-Complete.

In the previous studies, the researchers considered the Voronoi game in which the facilities are the same. In the real world, the customers usually consider both the preferences and the distances for shopping which is modeled by the multiplicity weighted Voronoi diagram. Accordingly, we introduce a new version of the Voronoi game for modeling this problem, called multiplicity weighted Voronoi diagram.

Material and methods

In this paper, the one-round weighted Voronoi game is studied in both one-dimensional and two-dimensional cases. In the multiplicity weighted Voronoi game, the customer can consider not only the distance of the facility but also its. Therefore, in the one-dimensional, two different models of the facility are considered and it is showed that the second player has a winning strategy in the one-round Voronoi game.

In the weighted Voronoi diagram, the points have the assigned weights according to their performance.

Firstly, we consider the topology of the cells of weighted Voronoi diagram whose edges are the parts of Apollonius circles and it is too complicated to calculate the areas of the weighted Voronoi cells. So Black just tries to earn a little more than White without calculating the exact amount of the winning area. Also, we assume that the sum of all weights of black points equals with the sum of the weights of all whites points, i.e., .

Results and discussion

In the one-dimensional model in which the area is a line segment, we study both the same-weight points and the different-weight points separately. We show that Black always has a winning strategy when the points have the same weight. In the other case, Black has a winning strategy when the variance of the distribution of the black points is less than or equal to the variance of the distribution of the white points.

In the two-dimensional model, we study the same-weight points and show that Black has a winning strategy.

Conclusion

In this study, we introduced the weighted Voronoi game to consider the performance of the facilities as well as the distance from customers. We showed that the second player has a winning strategy. In this model, customers can choose their service based on performances of the facilities such as parking, price, variety, quality of products, etc. Therefore this model is closer to the real world.

In the one-dimensional model, we showed that the second player can always win the game when the points have the same weight. Also, the second player can win the game with the different-weight points when the variance of the distribution of the black points is less than or equals the variance of the distribution of the white points. In the two-dimensional model, we showed that the black player can always win the one-round game../files/site1/files/61/5.pdf