Complexity of hidden polygon puzzle on square grids? Hiroimono 

 is a popular $NP$-complete puzzle. I'm interested in the computational complexity of a related puzzle. 

The problem is:

Input: Given a set of points on on a $n$x$n$ square grid and integer $k$ 

Question: Is there a rectilinear polygon (its sides parallel to the $x$ or $y$-axis) such that the number of points on the polygon's corners is at least $k$?

Every corner of the polygon must be at one of the input points (so bends are only allowed at an input point). 


  What is the complexity of this problem? What is the complexity if the solution restricted to convex rectilinear polygons? 


EDIT April 13: Alternate formulation: Find a rectilinear polygon with the maximum corners on the given points.
I thought of this weird reduction (chances that it is wrong are high :-). Idea: reduction from Hamiltonian path on grid graphs with degree $\leq 3$; each node of the planar graph can be shifted in such a way that every "row" ($y$ value) and every "column" ($x$ value) contains at most one node. The graph can be scaled and each node can be replaced by a square gadget with many points; horizontal links between the gadgets (the edges of the original graph) are made using pairs of points on distinct rows, vertical links using pair of points on distinct columns. Node traversals are forced using the "many points" of the square gadgets.

The node gadget is represented in the following figure:



It has 3 "interface points" $[W,N,E]$ (on distinct columns/rows), and an inner border of $C \times C$ points. A polyline that traverses the gadget from one interface point to another can have a number of corners that is proportional to $C$ (three traversals of the gadget are shown in the figure), in particular the number of corner points is between $2C$ and $2C+2$ (the total number of points of the gadget is $C \times C - 4 + 6$).
The gadget can be rotated to get other interface point combinations ($[N,E,S]$, $[E,S,W]$, $[S,W,N]$).

Now we can shift the planar grid graph in such a way that for every pair of nodes $(x_1,y_1), (x_2,y_2)$, $x_1 \neq x_2$ and $y1 \neq y_2$. See the following figure of a simple $4 \times 3$ grid. Next, we can scale the graph and replace each node with the gadget above. At this stage each gadget is "isolated": a polyline cannot go from one gadget to another. 



Now we can simulate the edges of the original graph using pairs of points on the bottom or on the right, each pair on a separate row or on a separate column; see the following figure for two adjacent nodes linked horizontally (in a new bottom row two points are added one on the same column of interface point $E$ of the first gadget, the other on the same column of interface point $W$ of the second gadget).



On every gadget there can be max $4 + 2C$ corner points (1 generated by the enter interface point, 1 generated by the exit interface point, 2 generated by the extra turn on straight traversals and 2C on the inner zig-zag), the points used for the edges can generate max $2e$ corner points. 

Suppose that the original graph has $n$ nodes and $e$ edges, if we pick $C &gt; (4n+2e)$, and $k = 2Cn$ as the number of corner points that must be used, then we force the "hidden" polygon of the puzzle to traverse every gadget; but every gadget can be entered/exited exactly once (through a pair of interface cells); so the problem has a solution if and only if the original grid graph has an Hamiltonian path.