Volume 6, Issue 1 (Vol. 6, No. 1 2020)
mmr 2020, 6(1): 47-56 |
Back to browse issues page
Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
Hassani1 Z, Eskandari M. On the facility location problem: One-round weighted Voronoi game. mmr 2020; 6 (1) :47-56
URL: http://mmr.khu.ac.ir/article-1-2689-en.html
URL: http://mmr.khu.ac.ir/article-1-2689-en.html
Abstract: (2596 Views)
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
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
Keywords: Computational geometry, Competitive facility location, Voronoi diagram, Multiplicative Voronoi diagram, Voronoi game.e.
Type of Study: S |
Subject:
alg
Received: 2017/10/11 | Revised: 2020/07/8 | Accepted: 2018/10/29 | Published: 2020/01/25 | ePublished: 2020/01/25
Received: 2017/10/11 | Revised: 2020/07/8 | Accepted: 2018/10/29 | Published: 2020/01/25 | ePublished: 2020/01/25
| Rights and permissions | |
 |
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. |
