4 ms·
This can be formally solved by constructing the arrangement of lines passing through each set of two points, then computing the dual of the arrangement. The ce
by eruci 7y ago
This can be formally solved by constructing the arrangement of lines passing through each set of two points, then computing the dual of the arrangement.
The cell with the maximum depth on the arrangement contains the points in the "middle", meaning they have as many points on one side, as they have on the other.
Then you can prove that a line starting on any such point will visit every other point an infinite number of times.
- boyobo 7y agoJust pick a point and rotate a line around that point continuously. Keep track of the number of points on the left. Since this count is essentially continuous (the jumps are of size 1), at some point during this rotation you will have an almost-balanced configuration (same number of points on left and right, up to parity error).
- eruci 7y agoYes, but it must be a point with certain properties, such that the same number of points are on either side of the line initially, otherwise, it would not work.
- boyobo 7y agoI am giving an alternate proof of your implicit statement "There exists a line which has the same number of points on each side". You did this by computing duals of cell arrangements. I am arguing that you don't need to do that. The proof I outlined will work for any point. Initially it might have the wrong number of points on both sides but for some rotation it will have the correct number of points on both sides.