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