Nothing Special   »   [go: up one dir, main page]
Skip to main content
SpringerLink
Log in

Convex Grabbing Game of the Point Set on the Plane

  • Original Paper
  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

Abstract

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8

Similar content being viewed by others

References

  1. Chaplick, S., Micek, P., Ueckerdt, T., Wiechert, V.: A note on concurrent graph sharing games. Integers 16, 5 (2016). Paper No. G1

    MathSciNet  MATH  Google Scholar 

  2. Cibulka, J., Kynčl, J., Mészáros, V., Stolař, R., Valtr, P.: Graph sharing games: complexity and connectivity. Theoret. Comput. Sci. 494, 49–62 (2013)

    Article  MathSciNet  Google Scholar 

  3. Cibulka, J., Kynčl, J., Mészáros, V., Stolař, R., Valtr, P.: Solution to Peter Winkler’s pizza problem, Combinatorial Algorithms. Lecture Notes Comput. Sci. 5874, 356–367 (2009)

    Article  Google Scholar 

  4. Egawa, Y., Enomoto, H., Matsumoto, N.: The graph grabbing game on \(K_{m, n}\)-trees. Discrete Math. 341, 1555–1560 (2018)

    Article  MathSciNet  Google Scholar 

  5. Knauer, K., Micek, P., Ueckerdt, T.: How to eat \(4/9\) of a pizza. Discrete Math. 311, 1635–1645 (2011)

    Article  MathSciNet  Google Scholar 

  6. Micek, P., Walczak, B.: A graph-grabbing game. Combin. Probab. Comput. 20, 623–629 (2011)

    Article  MathSciNet  Google Scholar 

  7. Micek, P., Walczak, B.: Parity in graph sharing games. Discrete Math. 312, 1788–1795 (2012)

    Article  MathSciNet  Google Scholar 

  8. Seacrest, D.E., Seacrest, T.: Grabbing the gold. Discrete Math. 312, 1804–1806 (2012)

    Article  MathSciNet  Google Scholar 

  9. Winkler, P.M.: Mathematical puzzles: a connoisseur’s collection. A K Peters, Natick, MA (2003)

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Research Institute for Digital Media and Content, Keio University, Yokohama, Kanagawa, Japan

    Naoki Matsumoto

  2. Shonan Institute of Technology, Fujisawa, Kanagawa, Japan

    Tomoki Nakamigawa

  3. Faculty of Science, Yamagata University, Yamagata, Japan

    Tadashi Sakuma

Authors
  1. Naoki Matsumoto
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Tomoki Nakamigawa
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Tadashi Sakuma
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Naoki Matsumoto.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Matsumoto, N., Nakamigawa, T. & Sakuma, T. Convex Grabbing Game of the Point Set on the Plane. Graphs and Combinatorics 36, 51–62 (2020). https://doi.org/10.1007/s00373-019-02117-z

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-019-02117-z

Keywords

Search

Navigation