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