Complexity of the Hidden Polygon Puzzle

The Hidden Polygon Puzzle (for brevity HPP) decision problemĀ  is:

Input: a set $P$ of $m$ integer points on a $n \times n$ square grid and an integer $k \leq m$;

Question: does exist a simple rectilinear polygon with $k$ or more vertices $(v_1,v_2, …, v_t), \; v_i \in P, t \geq k$?

The following figure shows an example of a HPP puzzle.

Hidden Polygon PuzzleFigure 1: Given the 21 points on the right, can we find
a simple rectilinear polygon with at least 16 vertices?
A possible solution is shown on the right.

The problem is a slight variant of the $\sf{NP}$-complete puzzle game Hiroimono; we prove that the Hidden Polygon Puzzle isĀ  $\sf{NP}$-complete, too using a completely different reduction.

click here to download the paper

Leave a Reply

Your email address will not be published. Required fields are marked *