Convex Grabbing Game of the Point Set on the Plane

Autor:	Tadashi Sakuma, Naoki Matsumoto, Tomoki Nakamigawa
Rok vydání:	2020
Předmět:	Convex hull Computer Science::Computer Science and Game Theory Plane (geometry) Point set 0211 other engineering and technologies Zero (complex analysis) Regular polygon 021107 urban & regional planning 0102 computer and information sciences 02 engineering and technology 01 natural sciences Theoretical Computer Science Combinatorics 010201 computation theory & mathematics Discrete Mathematics and Combinatorics Point (geometry) General position Mathematics
Zdroj:	Graphs and Combinatorics. 36:51-62
ISSN:	1435-5914 0911-0119
DOI:	10.1007/s00373-019-02117-z
Popis:	We introduce a new combinatorial game of a weighted point set P on the plane in general position, called a convex grabbing game. In the game, two players alternately remove a point on the convex hull of P and 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.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::c1b446c0e0d1ba0c929be6bdefb50f25 https://doi.org/10.1007/s00373-019-02117-z Zobrazit plný text záznamu Plný text ve formátu PDF Plný text ve formátu HTML
Nepřihlášeným uživatelům se plný text nezobrazuje	K zobrazení výsledku je třeba se přihlásit.