This approach can work. If all the points would have different $y$ coordinates it is easy to separate the bottom two by a horizontal line. But if some points have the same $y$ coordinate we can just rotate the points around the origin by some angle.
Since there is only a finite number of pairs of points, and any given pair can have the same $y$ coordinate under only $2$ different angles of rotation. So there must be some angle such that all points end up with different $y$ coordinates.
I didn't understand what you wrote at all.
Here is my solution to the problem.
A) We present the even $n$ case.
Mark the $n$ numbers $ n, n, n-1, n-1, n-2, n-2, \ldots , \lceil \frac{n+1}{2} \rceil, \lceil \frac{n+1}{2} \rceil $.
There must be one of these which is adjacent to an unmarked number. Draw a line segment between these 2, and then ignore them.
Of the remaining $n-1$ marked numbers and $n-1$ unmarked numbers, likewise we can find an adjacent pairing of marked-unmarked. Draw a line segment between these 2, and then ignore them.
Repeat this till we're done pairing all of the numbers.
Clearly, each line segment is tagged with the marked number, so there are exactly $ \lceil \frac{n}{2} \rceil$ of them.
The odd $n$ case is similar, just having to account for the last term. It is left as an exercise to the reader.
B) You made the observation that "A necessary (though not sufficient) condition for these line segments to not intersect, is that they must connect an odd parity to an even parity." This helps greatly with this part.
In the even parity positions, place the numbers $ n, n, n-1, n-1, n-2, n-2, \ldots , \lceil \frac{n+1}{2} \rceil $ (the number of copies of the last term depend on the parity of $n$) in any order.
In the odd parity positions, place the numbers $1, 1, 2, 2, \ldots $ in any order.
Then, clearly for any odd-even pairing, the greatest integer is that on the even parity index. Hence, this positioning uses exactly $ \lceil \frac{n}{2} \rceil $ tags.
Best Answer
You did not show that the process of reconnecting points decreases the number of crossings, nor in which order the points get connected initially.
One correct way to connect the points is to order them by increasing $x$-coordinate, then increasing $y$-coordinate, producing a list $p_1,p_2,\dots,p_{2n}$. Then hook up $p_1p_2,p_3p_4$ and so on. For a given segment $p_ip_{i+1}$, because of the no-three-in-line condition there can be at most one point with the same $x$-coordinate as $p_i$ and $p_{i+1}$, and if such points exist it's easy to show that their segments cannot cross $p_ip_{i+1}$. Otherwise, the fact that $p_ip_{i+1}$ partitions the set of $x$-coordinates into two disjoint intervals guarantees no crossings.