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.