Complexity of a matching problem on the grid $\mathbb Z^2$

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

-

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.

-