5
$\begingroup$

Given $2n$ integral points of $\mathbb Z^2$, is there a polynomial algorithm which gives a matching consisting of $n$ non-intersecting straight vertical or horizontal segments between pairs of points if such a matching exists? (Not all segments have to be vertical or horizontal, there can be $a$ vertical and $n-a$ horizontal segments, but two distinct segments do never intersect.)

Examples: (1) If the number of points is even in every row (or column) one can simply pair points row by row.

(2) No such matching exists for the four points $\pm (1,0),\pm (0,1)$.

There is also an obvious generalization to $\mathbb Z^d$ for $d\geq 3$.

PS: There is always a solution using piecewise linear paths with vertical or horizontal steps making at most one quarter of a turn (ie. either straight horizontal or vertical segments or L-shaped (and its rotations) paths).

Improve this question
$\endgroup$

2 Answers 2

Reset to default
6
$\begingroup$

I believe the full details, along the lines of what domotorp posted, are provided in "Reconstructing sets of orthogonal line segments in the plane" by Rendl and Woeginger. From the abstract,

"We show that reconstructing a set of $n$ orthogonal line segments in the plane from the set of their vertices can be done in $O(n log n)$ time, if the segments are allowed to cross. If the segments are not allowed to cross, the problem becomes NP-complete."

The authors give a reduction to planar 3-SAT that uses points on an integer lattice, which I believe is the setting you're interested in.

Improve this answer
$\endgroup$
1
$\begingroup$

I am almost sure this problem is NP-complete. The reduction is from Planar 1-in-3-SAT, where we are given a 3CNF and a planar bipartite graph whose vertices are the variables and the clauses, with an edge between them if the corresponding variable is in the given clause. A very sketchy reduction is to start for each variable with 4k points, where k is the number of its occurrences, e.g. with (0,1),(0,2),..,(0,k),(1,0),..,(k,0),(k+1,1),..,(k+1,k),(1,k+1),..,(k,k+1), so we either take k horizontal or k vertical segments. Then our choice is led through a polygonal path to the clause component, which is another simple gadget that requires one incoming path.

I know this is not a full proof, in fact I might be wrong, but working out the details is usually a tedious job that goes beyond a MO answer...

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .