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