3 papers
cs.CG2022
The Shortest Path with Increasing Chords in a Simple Polygon
Mart Hagedoorn, Irina Kostitsyna
We study the problem of finding the shortest path with increasing chords in a simple polygon. A path has increasing chords if and only if for any points a, b, c, and d that lie on…
cs.CG2021
Dots & Boxes is PSPACE-complete
Kevin Buchin, Mart Hagedoorn, Irina Kostitsyna +1
Exactly 20 years ago at MFCS, Demaine posed the open problem whether the game of Dots & Boxes is PSPACE-complete. Dots & Boxes has been studied extensively, with for instance a cha…
cs.CG2020
Dots & Polygons
Kevin Buchin, Mart Hagedoorn, Irina Kostitsyna +3
We present a new game, Dots & Polygons, played on a planar point set. Players take turns connecting two points, and when a player closes a (simple) polygon, the player scores its a…