LIPIcs.SoCG.2020.79.pdf
- Filesize: 499 kB
- 4 pages
Document
Dots & Polygons (Media Exposition)
Authors
Kevin Buchin 
,
Irina Kostitsyna ,
-
Part of:
Volume:
36th International Symposium on Computational Geometry (SoCG 2020)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-06-08
File
Document Identifiers
Author Details
Acknowledgements
We would like to thank David Eppstein for discussing [Eppstein, 2020] with us.
Cite As Get BibTex
Kevin Buchin, Mart Hagedoorn, Irina Kostitsyna, Max van Mulken, Jolan Rensen, and Leo van Schooten. Dots & Polygons (Media Exposition). In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 79:1-79:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.SoCG.2020.79
Abstract
We present a new game, Dots & Polygons, played on a planar point set. We prove that its NP-hard and discuss strategies for the case when the point set is in convex position.
Subject Classification
ACM Subject Classification
- Theory of computation → Computational geometry
Keywords
- Dots & Boxes
- NP-hard
- game
- cycle packing
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Oswin Aichholzer, David Bremner, Erik D. Demaine, Ferran Hurtado, Evangelos Kranakis, Hannes Krasser, Suneeta Ramaswami, Saurabh Sethia, and Jorge Urrutia. Games on triangulations. Theoretical Computer Science, 343(1–2):52-54, 2005.
-
Sander Beekhuis, Kevin Buchin, Thom Castermans, Thom Hurks, and Willem Sonke. Ruler of the plane - games of geometry (multimedia contribution). In 33rd International Symposium on Computational Geometry (SoCG), volume 77 of LIPIcs, pages 63:1-63:5. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.
-
Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars. Computational geometry: algorithms and applications. Springer, 2008.
-
Elwyn R. Berlekamp. The Dots and Boxes Game: Sophisticated Child’s Play. AK Peters/CRC Press, 2000.
-
Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy. Chapter 16: Dots-and-boxes. In Winning Ways for your Mathematical Plays, volume 3, pages 541-584. A K Peters/CRC Press, 2nd edition, 2003.
-
Hans L. Bodlaender. On disjoint cycles. In Graph-Theoretic Concepts in Computer Science, pages 230-238, Berlin, Heidelberg, 1992. Springer Berlin Heidelberg.
- Kevin Buchin, Mart Hagedoorn, Irina Kostitsyna, Max van Mulken, Jolan Rensen, and Leo van Schooten. Dots & polygons, 2020. URL: http://arxiv.org/abs/2004.01235.
-
Alberto Caprara and Romeo Rizzi. Packing triangles in bounded degree graphs. Information Processing Letters, 84(4):175-180, 2002.
- David Eppstein. Computational complexity of games and puzzles. Last accessed on 14/02/2020. URL: https://www.ics.uci.edu/~eppstein/cgt/hard.html.
-
Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., USA, 1979.
-
Ronald L. Graham. An efficient algorithm for determining the convex hull of a finite planar set. Information Processing Letters, 1:132-133, 1972.
- Sian Zelbo. Dots and polygons game. Last accessed on 14/02/2020. URL: http://www.1001mathproblems.com/2015/03/for-printable-game-boards-click-here.html.