On Tue, 5 Jan 2021, 15:46 Dan Asimov, <asimov@msri.org> wrote:
Let T^2 = R^2/Z^2 denote the square torus, i.e., a unit square with its opposite edges identified. Let X = {x_1, ..., x_n} be any set of n distinct points of T^2 where n = 2k is even. Does there necessarily exist n/2 disjoint line segments in T^2 whose n endpoints form the entire set X ??? Proof or counterexample.
Yes. Proof: Let's call "column" each class of points which have the same x coordinate. Start with the first column (least x coordinate). The largest possible even number of points in that column can be connected within that column, forming pairs of points of increasing y coordinate. So there remains at most one point in that column left. Connect it with the closest point of the next column (next larger x coordinate). Go on in the same way with that column (forming pairs of points with neighbouring y-coordinates, of course without crossing the point that has probably been used to pair with the last remaining one of the previous column. There is obviously no intersection amongst these line segments. When X is such that there does exist such a collection of n/2 disjoint line
segments, can they always be chosen so as to be *shortest* line segments???
Shortest between the given pairs of points, yes. It's sufficient to tweak the above construction a little to avoid that a point has to be connected with a point at distance > 0.5 which could happen if we made an unfortunate choice for a non-vertical connection. (Example: if in the second column there are 3 points (say P2, P3 and P4) at x= 0, 0.1 and 0.2 , and we connected the one at 0.1 (i.e. P3) to the last remaining point P1of the first column. Then according to the prescription, the two other points (P2 and P4) have to be connected using a segment of length 0.8. But when this would occur, then we can necessarily connect the remaining point of the previous column (P1) to one of the neighbors (P2 or P4) instead of the initial choice (P3), using only vertical segments of length < 0.5, and non-vertical segments which are also "shortest" ones. (At worst it may be necessary to switch the order of processing columns, from going by increasing x-coordinates to decreasing x-coordinates.) (If points p and q of T^2 are less than the maximum possible distance of
√(1/2) apart, then there is a unique shortest segment connecting them.
I think that's not true. They can also be at distance 0.5 with two distinct possibilities of connecting them with segments of equal length, e.g. when both have y=0 and one has x=0 and the other has x=0.5. One can connect them either with the segment {(x,0) ; 0 <= x <= 0.5 } or with the distinct segment {(x,0) ; 0.5 <= x <= 1 }. So the segment of minimal length is not unique in that case where the distance is 0.5 < 0.707 < √(1/2). - Maximilian
If their distance is √(1/2) then there are four such segments.)