جانمایی رقابتی تسهیلات با بازی ورونوی وزن دارتک دوری

بازی ورونوی، یک مدل هندسی ساده برای مسائل جانمایی رقابتی تسهیلات با دو بازیکن ارائه می دهد. بازی ورونوی با دو بازیکن (سفید و سیاه)، در یک ناحیه پیوسته و محدود (یک بعدی یا دو بعدی) به‌عنوان صفحه بازی، انجام می شود. در مدل تک دوری، ابتدا بازیکن سفید تمامی مهره های خود را که نقطه هستند، روی صفحه بازی قرار می دهد. سپس نوبت به بازیکن سیاه می رسد تا تمامی نقاط خود را قرار دهد. سپس صفحه بازی براساس معیار نزدیکی فاصله، بین دو بازیکن تقسیم شده و بازیکنی که مساحت بیش‌تری از ناحیۀ بازی را از آن خود کرده است، برنده بازی شناخته می شود. در این مقاله، بازی ورونوی وزن دار تک دوری در نواحی یک بعدی و دو بعدی بررسی می شود. در بازی ورونوی وزن دار، سرویس گیرندگان می توانند علاوه بر معیار نزدیکی فاصله برای انتخاب سرویس دهنده، کیفیت امکانات آن را نیز مد نظر قرار دهند. براین اساس، در ناحیه یک بعدی دو حالت مختلف از تسهیلات (همسان و غیرهمسان) را بررسی می‌کنیم و نشان می دهیم در بازی ورونوی وزن دار تک دوری بازیکن سیاه دارای استراتژی برد است.

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

Paper pages (4756)IntroductionThe 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 (onedimensional or twodimensional). In the oneround 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 twodimensional version of Voronoi game on a rectangular area of aspect ratio rho;. 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 NPComplete.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 methodsIn this paper, the oneround weighted Voronoi game is studied in both onedimensional and twodimensional cases. In the multiplicity weighted Voronoi game, the customer can consider not only the distance of the facility but also its. Therefore, in the onedimensional, two different models of the facility are considered and it is showed that the second player has a winning strategy in the oneround 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 discussionIn the onedimensional model in which the area is a line segment, we study both the sameweight points and the differentweight 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 twodimensional model, we study the sameweight points and show that Black has a winning strategy.ConclusionIn 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 onedimensional 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 differentweight 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 twodimensional model, we showed that the black player can always win the oneround game../files/site1/files/61/5.pdf