Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question
4  
Shouldn't convex rectilinear polygons be solvable in polynomial time by dynamic programming? –  Peter Shor Nov 5 '10 at 14:22
4  
Yes, it should. –  JɛffE Nov 5 '10 at 14:25
    
@JeffE, How about the general non-convex case? What is your inclination? –  Mohammad Al-Turkistany Nov 5 '10 at 20:01
2  
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 Nov 6 '10 at 4:19
5  
@Suresh Just a note: googling around I found that planar version of NAE3SAT is in P (portal.acm.org/…). –  Marzio De Biasi Mar 12 '11 at 21:13

2 Answers 2

up vote 6 down vote accepted

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

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

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

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.

share|improve this answer

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," 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.