How can u find every possible division of $2n$ points into 2 sets each containing $n$ points, with the condition, that these two sets need to be divisible by a line (for a 2 dimensional space).
My initial thoughts are the following, but i got stuck:
- Order the point by one coordinate (lets say the x-coordinate for example).
- Divide the points into 2 sets by 'cutting' the sorted points in the middle
- This could be represented by a line dividing the two sets.
- Now my idea is to somehow turn the line either clockwise or anti-clockwise until we arrive at our starting configuration.
Does anyone know a solution to my problem ?
There are at most ${2n \choose 2}$ lines $L_j$ containing at least two of your points. So for all but finitely many angles $\theta$, you can order your points by the dot product with the unit vector ${\bf u} = (\cos(\theta), \sin(\theta))$ and have no ties: there will be a line orthogonal to $\bf u$ that splits the points into two sets of $n$. Moreover, if $\theta_1, \theta_2$ are angles orthogonal to two of those $L_j$ with no $L_j$ orthogonal to an angle between $\theta_1$ and $\theta_2$, all $\theta$'s in the open interval from $\theta_1$ to $\theta_2$ give the same splitting. So just sample one $\theta$ in each of the intervals and you're sure of getting all of them.