|
|
پژوهش های ریاضی، جلد ۶، شماره ۱، صفحات ۴۷-۵۶
|
|
|
| عنوان فارسی |
جانمایی رقابتی تسهیلات با بازی ورونوی وزن دارتک دوری |
|
| چکیده فارسی مقاله |
بازی ورونوی، یک مدل هندسی ساده برای مسائل جانمایی رقابتی تسهیلات با دو بازیکن ارائه میدهد. بازی ورونوی با دو بازیکن (سفید و سیاه)، در یک ناحیه پیوسته و محدود (یک بعدی یا دو بعدی) بهعنوان صفحه بازی، انجام میشود. در مدل تک دوری، ابتدا بازیکن سفید تمامی مهرههای خود را که نقطه هستند، روی صفحه بازی قرار میدهد. سپس نوبت به بازیکن سیاه میرسد تا تمامی نقاط خود را قرار دهد. سپس صفحه بازی براساس معیار نزدیکی فاصله، بین دو بازیکن تقسیم شده و بازیکنی که مساحت بیشتری از ناحیۀ بازی را از آن خود کرده است، برنده بازی شناخته میشود. در این مقاله، بازی ورونوی "وزندار" تک دوری در نواحی یک بعدی و دو بعدی بررسی میشود. در بازی ورونوی وزندار، سرویسگیرندگان میتوانند علاوه بر معیار نزدیکی فاصله برای انتخاب سرویسدهنده، کیفیت امکانات آن را نیز مد نظر قرار دهند. براین اساس، در ناحیه یک بعدی دو حالت مختلف از تسهیلات (همسان و غیرهمسان) را بررسی میکنیم و نشان میدهیم در بازی ورونوی وزندار تک دوری بازیکن سیاه دارای استراتژی برد است. |
|
| کلیدواژههای فارسی مقاله |
هندسۀ محاسباتی، جانمایی رقابتی تسهیلات، دیاگرام ورونوی، دیاگرام ورونوی وزن دار مضربی، بازی ورونوی |
|
| عنوان انگلیسی |
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
![""]("file:///C:Users1AppDataLocalTempmsohtmlclip11clip_image002.gif") 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 ![""]("file:///C:Users1AppDataLocalTempmsohtmlclip11clip_image004.gif") with![""]("file:///C:Users1AppDataLocalTempmsohtmlclip11clip_image006.gif") and for ![""]("file:///C:Users1AppDataLocalTempmsohtmlclip11clip_image008.gif") with ![""]("file:///C:Users1AppDataLocalTempmsohtmlclip11clip_image010.gif") 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., ![""]("file:///C:Users1AppDataLocalTempmsohtmlclip11clip_image012.gif") .
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
|
|
| کلیدواژههای انگلیسی مقاله |
Computational geometry, Competitive facility location, Voronoi diagram, Multiplicative Voronoi diagram, Voronoi game.e. |
|
| نویسندگان مقاله |
زینب حسنی | Zeinab Hassani1
دانشگاه تحصیلات تکمیلی علوم پایه زنجان، دانشکده علوم کامپیوتر و فناوری اطلاعات، دانشگاه کوثر، دانشکده علوم پایه و فنی، گروه کامپیوتر، بجنورد، ایران.
مرضیه اسکندری | Marzieh Eskandari
دانشگاه الزهرا، دانشکدۀ علوم ریاضی، گروه کامپیوتر
|
|
| نشانی اینترنتی |
http://mmr.khu.ac.ir/browse.php?a_code=A-10-361-2&slc_lang=fa&sid=1 |
| فایل مقاله |
فایلی برای مقاله ذخیره نشده است |
| کد مقاله (doi) |
|
| زبان مقاله منتشر شده |
fa |
| موضوعات مقاله منتشر شده |
جبر |
| نوع مقاله منتشر شده |
علمی پژوهشی بنیادی |
|
|
|
برگشت به:
صفحه اول پایگاه |
نسخه مرتبط |
نشریه مرتبط |
فهرست نشریات
|
