Dots & polygons (Media Exposition)

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

doi:10.4230/LIPIcs.SoCG.2020.79

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 proceeding › Conference contribution › Academic › peer-review

1 Citation (Scopus)

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 language	English
Title of host publication	36th International Symposium on Computational Geometry (SoCG)
Editors	Sergio Cabello, Danny Z. Chen
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
ISBN (Electronic)	9783959771436
DOIs	https://doi.org/10.4230/LIPIcs.SoCG.2020.79
Publication status	Published - 1 Jun 2020
Event	36th International Symposium on Computational Geometry, SoCG 2020 - Zurich, Switzerland Duration: 23 Jun 2020 → 26 Jun 2020

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	164
ISSN (Print)	1868-8969

Conference

Conference	36th International Symposium on Computational Geometry, SoCG 2020
Country/Territory	Switzerland
City	Zurich
Period	23/06/20 → 26/06/20

Funding

We would like to thank David Eppstein for discussing [9] with us.

Keywords

Boxes
Cycle packing
Dots
Game
NP-hard

Access to Document

10.4230/LIPIcs.SoCG.2020.79

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) Article 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

@inproceedings{4a0fda2b3442455f95dcb1960876573c,

title = "Dots \& polygons (Media Exposition)",

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.",

keywords = "Boxes, Cycle packing, Dots, Game, NP-hard",

author = "Kevin Buchin and Mart Hagedoorn and Irina Kostitsyna and \{van Mulken\}, Max and Jolan Rensen and \{van Schooten\}, Leo",

year = "2020",

month = jun,

day = "1",

doi = "10.4230/LIPIcs.SoCG.2020.79",

language = "English",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

editor = "Sergio Cabello and Chen, \{Danny Z.\}",

booktitle = "36th International Symposium on Computational Geometry (SoCG)",

note = "36th International Symposium on Computational Geometry, SoCG 2020 ; Conference date: 23-06-2020 Through 26-06-2020",

}

Buchin, K, Hagedoorn, M, Kostitsyna, I, van Mulken, M, Rensen, J & van Schooten, L 2020, Dots & polygons (Media Exposition). in S Cabello & DZ 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, 36th International Symposium on Computational Geometry, SoCG 2020, Zurich, Switzerland, 23/06/20. https://doi.org/10.4230/LIPIcs.SoCG.2020.79

Dots & polygons (Media Exposition). / Buchin, Kevin; Hagedoorn, Mart; Kostitsyna, Irina et al.
36th International Symposium on Computational Geometry (SoCG). ed. / Sergio Cabello; Danny Z. Chen. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. LIPIcs-SoCG-2020-79 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 164).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Dots & polygons (Media Exposition)

AU - Buchin, Kevin

AU - Hagedoorn, Mart

AU - Kostitsyna, Irina

AU - van Mulken, Max

AU - Rensen, Jolan

AU - van Schooten, Leo

PY - 2020/6/1

Y1 - 2020/6/1

N2 - 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.

AB - 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.

KW - Boxes

KW - Cycle packing

KW - Dots

KW - Game

KW - NP-hard

UR - https://www.scopus.com/pages/publications/85086503259

U2 - 10.4230/LIPIcs.SoCG.2020.79

DO - 10.4230/LIPIcs.SoCG.2020.79

M3 - Conference contribution

AN - SCOPUS:85086503259

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 36th International Symposium on Computational Geometry (SoCG)

A2 - Cabello, Sergio

A2 - Chen, Danny Z.

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

T2 - 36th International Symposium on Computational Geometry, SoCG 2020

Y2 - 23 June 2020 through 26 June 2020

ER -

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