Mathematical Researches
پژوهش های ریاضی
mmr
Basic Sciences
http://mmr.khu.ac.ir
1
admin
2588-2546
2588-2554
10.61186/mmr
fa
jalali
1399
2
1
gregorian
2020
5
1
6
1
online
1
fulltext
fa
جانمایی رقابتی تسهیلات با بازی ورونوی وزن دارتک دوری
On the facility location problem: One-round weighted Voronoi game
جبر
alg
علمی پژوهشی بنیادی
S
<span style="color:black;"><span style="font-family:B Nazanin;"><span style="font-size:10.0pt;">بازی ورونوی، یک مدل هندسی ساده برای مسائل جانمایی رقابتی تسهیلات با دو بازیکن</span></span></span> <span style="color:black;"><span style="font-family:B Nazanin;"><span style="font-size:10.0pt;">ارائه می­دهد. بازی ورونوی با دو بازیکن (سفید و سیاه)، در یک ناحیه پیوسته</span></span></span> <span style="color:black;"><span style="font-family:B Nazanin;"><span style="font-size:10.0pt;">و محدود (یک بعدی یا دو بعدی) بهعنوان صفحه بازی، انجام می­شود. در مدل تک دوری، ابتدا بازیکن سفید تمامی مهره­های خود را که نقطه هستند، روی صفحه بازی قرار می­دهد. سپس نوبت به بازیکن سیاه می­رسد تا تمامی نقاط خود را قرار دهد. سپس صفحه بازی براساس معیار نزدیکی فاصله، بین دو بازیکن تقسیم شده و بازیکنی که مساحت بیشتری از ناحیۀ بازی را از آن خود کرده است، برنده بازی شناخته می­شود. در این مقاله، بازی ورونوی "وزن­دار" تک دوری در نواحی یک بعدی و دو بعدی بررسی می­شود. در بازی ورونوی وزن­دار، سرویس­گیرندگان می­توانند علاوه بر معیار نزدیکی فاصله برای انتخاب سرویس­دهنده، کیفیت امکانات آن را نیز مد نظر قرار دهند. براین اساس، در ناحیه یک بعدی دو حالت مختلف از تسهیلات (همسان و غیرهمسان) را بررسی میکنیم و نشان می­دهیم در بازی ورونوی وزن­دار تک دوری بازیکن سیاه دارای استراتژی برد است.</span></span></span>
Paper pages (47-56)<br>
<strong>Introduction</strong><br>
The Voronoi game is a simple geometric model for competitive facility location problem which is played by two players, Whi<a name="_GoBack"></a>te 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.<br>
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<br>
<img alt="" height="19" src="file:///C:Users1AppDataLocalTempmsohtmlclip11clip_image002.gif" width="33" > 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 <img alt="" height="19" src="file:///C:Users1AppDataLocalTempmsohtmlclip11clip_image004.gif" width="39" > with<img alt="" height="20" src="file:///C:Users1AppDataLocalTempmsohtmlclip11clip_image006.gif" width="67" > and for <img alt="" height="19" src="file:///C:Users1AppDataLocalTempmsohtmlclip11clip_image008.gif" width="42" > with <img alt="" height="20" src="file:///C:Users1AppDataLocalTempmsohtmlclip11clip_image010.gif" width="60" > 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.<br>
In the previous studies, the researchers considered the Voronoi game in which the facilities are the same<span dir="RTL">.</span> 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<strong>.</strong><br>
<strong>Material and methods</strong><br>
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.<br>
In the weighted Voronoi diagram, the points have the assigned weights according to their performance.<br>
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., <img alt="" height="19" src="file:///C:Users1AppDataLocalTempmsohtmlclip11clip_image012.gif" width="153" >.<br>
<strong>Results and discussion</strong><br>
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.<br>
In the two-dimensional model, we study the same-weight points and show that Black has a winning strategy.<br>
<strong>Conclusion</strong><br>
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.<br>
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.<a href="./files/site1/files/61/5.pdf">./files/site1/files/61/5.pdf</a><span dir="RTL"></span><br>
<br>
هندسۀ محاسباتی, جانمایی رقابتی تسهیلات, دیاگرام ورونوی, دیاگرام ورونوی وزن دار مضربی, بازی ورونوی
Computational geometry, Competitive facility location, Voronoi diagram, Multiplicative Voronoi diagram, Voronoi game.e.
47
56
http://mmr.khu.ac.ir/browse.php?a_code=A-10-361-2&slc_lang=fa&sid=1
Zeinab
Hassani1
زینب
حسنی
10031947532846003584
10031947532846003584
Yes
دانشگاه تحصیلات تکمیلی علوم پایه زنجان، دانشکده علوم کامپیوتر و فناوری اطلاعات، دانشگاه کوثر، دانشکده علوم پایه و فنی، گروه کامپیوتر، بجنورد، ایران.
Marzieh
Eskandari
مرضیه
اسکندری
eskandari@alzahra.ac.ir
10031947532846003585
10031947532846003585
No
دانشگاه الزهرا، دانشکدۀ علوم ریاضی، گروه کامپیوتر