<p>Not an answer, just a few references.  First, I wrote a paper (long ago!) on the case where
every point in the given set $V$ must be a polygon corner.  In that case, it is not surprising
that there is (at most) one polygon, and it is easy to find:
"Uniqueness of Orthogonal Connect-the-Dots,"
in <em>Computational Morphology</em>, Ed. G. T. Toussaint,
Elsevier, North-Holland, 1988, 97-104.</p>

<p>Second, there is a beautiful update to this work by Maarten Löffler and Elena Mumford,
in a paper, 
"<a href="http://www.ics.uci.edu/~mloffler/publications/Connected_Rectilinear_Graphs_on_Point_Sets.html">Connected Rectilinear Graphs on Point Sets</a>,"
<em>Journal of Computational Geometry</em>,
2(1), 1–15, 2011.  From their Abstract:</p>

<blockquote>
  <p>We study the question whether there exists an orientation such that $V$ is the vertex set of a connected rectilinear graph in that orientation. ... We prove that at most one such orientation can be possible, up to trivial rotations of 90 degrees around some axis. </p>
</blockquote>

CC BY-SA 3.0
2011-04-13T01:07:12.100Z
2011-04-13T01:07:12.100Z
Joseph O'Rourke
<p>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.</p>

<p>The node gadget is represented in the following figure:</p>

<p><img src="https://i.sstatic.net/L4amL.jpg" alt="enter image description here"></p>

<p>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]$).</p>

<p>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. </p>

<p><img src="https://i.sstatic.net/8DksT.jpg" alt="enter image description here"></p>

<p>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).</p>

<p><img src="https://i.sstatic.net/F1aMk.jpg" alt="enter image description here"></p>

<p>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. </p>

<p>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. </p>

CC BY-SA 3.0
2012-12-03T20:09:57.547Z
2012-12-03T21:11:15.143Z
2012-12-03T21:11:15.143Z
Marzio De Biasi
<p><a href="https://doi.org/10.1007/978-3-540-72914-3_5" rel="nofollow noreferrer">Hiroimono</a> is a popular <span class="math-container">$NP$</span>-complete puzzle. I'm interested in the computational complexity of a related puzzle.</p>
<p>The problem is:</p>
<p><strong>Input</strong>: Given a set of points on on a <span class="math-container">$n$</span>x<span class="math-container">$n$</span> square grid and integer <span class="math-container">$k$</span></p>
<p><strong>Question</strong>: Is there a rectilinear polygon (its sides parallel to the <span class="math-container">$x$</span> or <span class="math-container">$y$</span>-axis) such that the number of points on the polygon's corners is at least <span class="math-container">$k$</span>?</p>
<p>Every corner of the polygon must be at one of the input points (so bends are only allowed at an input point).</p>
<blockquote>
<p>What is the complexity of this problem? What is the complexity if the solution restricted to convex rectilinear polygons?</p>
</blockquote>
<p>EDIT April 13: Alternate formulation: Find a rectilinear polygon with the maximum corners on the given points.</p>

CC BY-SA 2.5
2011-03-12T21:13:31.167Z
@Suresh Just a note: googling around I found that planar version of NAE3SAT is in P (http://portal.acm.org/citation.cfm?id=49097.49099&coll=GUIDE&dl=GUIDE).
Marzio De Biasi
CC BY-SA 2.5
2010-11-05T14:22:45.430Z
Shouldn't convex rectilinear polygons be solvable in polynomial time by dynamic programming?
Peter Shor 
CC BY-SA 2.5
2010-11-05T14:25:09.093Z
Yes, it should.
Jeffε
CC BY-SA 2.5
2010-11-05T20:01:59.080Z
@JeffE, How about the general non-convex case? What is your inclination?
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-11-05T23:13:47.597Z
My guess is that the non-convex case is NP-complete, but proving it is probably going to involve messing around with gadgets.
Peter Shor 
CC BY-SA 2.5
2010-11-06T04:17:24.547Z
Thanks Peter, Do you suggest any NP-complete problem for the reduction?
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-11-06T04:19:54.100Z
for many of these problems, your best bet is to start with something like planar 3SAT or even planar NAE-SAT. It will be horribly ugly, but the planarity gives you the structures you might need.
Suresh Venkat
CC BY-SA 2.5
2010-11-06T19:53:23.760Z
Thanks Suresh for your suggestion. Are you aware of any application for this problem?
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-11-07T18:46:08.080Z
not really, except that it seems like a weird variant of a prize-collecting TSP on the grid (the weirdness coming from the turn condition)
Suresh Venkat
CC BY-SA 2.5
2010-11-08T01:33:53.910Z
There's also a weirdness that comes from the polygon condition.
Peter Shor 
<cc.complexity-theory><np-hardness><puzzles><integer-lattice>
Complexity of hidden polygon puzzle on square grids?
Mohammad Al-Turkistany
# Complexity of hidden polygon puzzle on square grids?

(Asked by: username_0 on 2010-11-05)

[Hiroimono](https://doi.org/10.1007/978-3-540-72914-3_5) 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.

**Tags:** cc.complexity-theory, np-hardness, puzzles, integer-lattice
> **Comments:**
> **username_2**: Shouldn't convex rectilinear polygons be solvable in polynomial time by dynamic programming?  
> **username_3**: Yes, it should.  
> **username_0**: @JeffE, How about the general non-convex case? What is your inclination?  
> **username_2**: My guess is that the non-convex case is NP-complete, but proving it is probably going to involve messing around with gadgets.  
> **username_0**: Thanks Peter, Do you suggest any NP-complete problem for the reduction?  
> **username_4**: for many of these problems, your best bet is to start with something like planar 3SAT or even planar NAE-SAT. It will be horribly ugly, but the planarity gives you the structures you might need.  
> **username_0**: Thanks Suresh for your suggestion. Are you aware of any application for this problem?  
> **username_4**: not really, except that it seems like a weird variant of a prize-collecting TSP on the grid (the weirdness coming from the turn condition)  
> **username_2**: There's also a weirdness that comes from the polygon condition.  
> **username_1**: @Suresh Just a note: googling around I found that planar version of NAE3SAT is in P (http://portal.acm.org/citation.cfm?id=49097.49099&coll=GUIDE&dl=GUIDE).  

---

## 2 answers

### Answer by username_1 on 2012-12-03. Score: 6 | Accepted answer

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:

![enter image description here](https://i.sstatic.net/L4amL.jpg)

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.

![enter image description here](https://i.sstatic.net/8DksT.jpg)

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

![enter image description here](https://i.sstatic.net/F1aMk.jpg)

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


---

### Answer by username_5 on 2011-04-13. Score: 5

Not an answer, just a few references. First, I wrote a paper (long ago!) on the case where
every point in the given set $V$ must be a polygon corner. In that case, it is not surprising
that there is (at most) one polygon, and it is easy to find:
"Uniqueness of Orthogonal Connect-the-Dots,"
in *Computational Morphology*, Ed. G. T. Toussaint,
Elsevier, North-Holland, 1988, 97-104.

Second, there is a beautiful update to this work by Maarten Löffler and Elena Mumford,
in a paper,
"[Connected Rectilinear Graphs on Point Sets](http://www.ics.uci.edu/~mloffler/publications/Connected_Rectilinear_Graphs_on_Point_Sets.html),"
*Journal of Computational Geometry*,
2(1), 1–15, 2011. From their Abstract:

> We study the question whether there exists an orientation such that $V$ is the vertex set of a connected rectilinear graph in that orientation. ... We prove that at most one such orientation can be possible, up to trivial rotations of 90 degrees around some axis.


---

