Dots & polygons (Media Exposition)

Kevin Buchin, Mart Hagedoorn, Irina Kostitsyna, Max van Mulken, Jolan Rensen, Leo van Schooten

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

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.

Original languageEnglish
Title of host publication36th International Symposium on Computational Geometry (SoCG)
EditorsSergio Cabello, Danny Z. Chen
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
ISBN (Electronic)9783959771436
DOIs
Publication statusPublished - 1 Jun 2020
Event36th International Symposium on Computational Geometry, SoCG 2020 - Zurich, Switzerland
Duration: 23 Jun 202026 Jun 2020

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume164
ISSN (Print)1868-8969

Conference

Conference36th International Symposium on Computational Geometry, SoCG 2020
CountrySwitzerland
CityZurich
Period23/06/2026/06/20

Keywords

  • Boxes
  • Cycle packing
  • Dots
  • Game
  • NP-hard

Cite this

Buchin, K., Hagedoorn, M., Kostitsyna, I., van Mulken, M., Rensen, J., & van Schooten, L. (2020). Dots & polygons (Media Exposition). In S. Cabello, & D. Z. Chen (Eds.), 36th International Symposium on Computational Geometry (SoCG) [LIPIcs-SoCG-2020-79] (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 164). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2020.79