Convex Grabbing Game of the Point Set on the Plane
Convex Grabbing Game of the Point Set on the Plane
复制标题
平面上点集的凸抓取博弈
DOI：
10.1007/s00373-019-02117-z
复制
发表时间：
2019
影响因子：
0.7
通讯作者：
Tomoki Nakamigawa & Tadashi Sakuma
中科院分区：
文献类型：
--
作者：
Naoki Matsumoto ;Tomoki Nakamigawa & Tadashi Sakuma
我们引入了一种新的在一般位置的平面上设置权重点的组合游戏，称为凸抓取游戏。游戏中，两名玩家交替去除P凸包上的一个点，并获取去除点的权重作为自己的得分。每个玩家的目标是在所有分数都被拿走后最大化他们的分数。在本文中，我们证明第一个玩家总是可以在给定的奇点点集（最多有两个内点）上赢得比赛。此外，通过将每个点的权重限制为0或1，我们将上述结果中“最多两个”的条件放宽为“最多四个”。我们还表明，通过构建多个加权点集（其中第一个玩家无法赢得比赛），这些结果是最好的。
We introduce a new combinatorial game of a weighted point setPon the plane in general position, called aconvex grabbing game. In the game, two players alternately remove a point on the convex hull ofPand obtain the weight of the removed point as their score. Each player’s aim is to maximize their score, when all points have been taken. In this paper, we prove that the first player can always win the game on the given point set of odd points with at most two inner points. Moreover, by restricting the weight of each point to zero or one, we relax the condition “at most two” in the above result to “at most four”. We also show that these results are best possible by constructing several weighted point sets in which the first player cannot win the game.
登录
查看更多内容
Km、n 树上的图抓取游戏
影响因子：
0.8
作者：
Y. Egawa;H. Enomoto;Naoki Matsumoto
通讯作者：
Naoki Matsumoto
一个抓图游戏
DOI：
--
发表时间：
2011
期刊：
Combinatorics, probability & computing
影响因子：
--
作者：
Piotr Micek;Bartosz Walczak
通讯作者：
Bartosz Walczak
如何吃掉 4/9 的披萨
DOI：
10.1016/j.disc.2011.03.015
发表时间：
2008
期刊：
Discret. Math.
影响因子：
--
作者：
K. Knauer;Piotr Micek;T. Ueckerdt
通讯作者：
T. Ueckerdt
图共享游戏中的奇偶校验
DOI：
10.1016/j.disc.2012.01.037
发表时间：
2012
期刊：
Discret. Math.
影响因子：
--
作者：
Piotr Micek;Bartosz Walczak
通讯作者：
Bartosz Walczak
图共享游戏：复杂性和连通性
DOI：
10.1016/j.tcs.2012.12.029
发表时间：
2010
期刊：
ArXiv
影响因子：
--
作者：
Josef Cibulka;J. Kynčl;Viola Mészáros;R. Stolar;P. Valtr
通讯作者：
P. Valtr