[math-fun] Puzzle and question about pairing up points on the torus with disjoint segments
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. Puzzle: ------- Does there necessarily exist n/2 disjoint line segments in T^2 whose n endpoints form the entire set X ??? Proof or counterexample. (Note that on T^2 there are infinitely many line segments between points p and q.) Question: --------- 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??? (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. If their distance is √(1/2) then there are four such segments.) —Dan
On Tue, Jan 5, 2021 at 2:46 PM 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.
Puzzle: ------- Does there necessarily exist n/2 disjoint line segments in T^2 whose n endpoints form the entire set X ??? Proof or counterexample.
Yes. In fact, this is true of 2n points in the square, without the additional possibilities given by identifying the edges. If all the points have different y coordinates, just sort by y, and draw segments between the top 2, the next 2, etc. If some points have the same y coordinate, choose a small e such that all points have different values of z = y + e x, and sort by z instead of y.
(Note that on T^2 there are infinitely many line segments between points p and q.)
Question: --------- 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???
At first I thought the same construction still worked. I think it still does, but with a slight modification . Suppose we try choosing the same pairs of points, but use the shortest segment between the two points. This works if the shortest segment stays in the square, or if it "wraps around in the x direction", that is, using the identification of (0,y) with (1, y). But it can fail if the shortest segment wraps in the y direction. using the identification of (x, 0) and (x, 1). But this can only happen if the y-coordinates of the 2 points differ by >= 1/2. In this case, use the same pairing technique, but start just below this large gap in y-coordinates. That is, if the points include 2 points (x_1, y_1) and (x_2, y_2) with y_1 - y_2 >= 1/2, and with no other point (x_i, y_i) with y_2 <= y_i <= y_1 (note that this can happen for at most one pair of values y_1 and y_2), then sort by y as before, but sorting with all values of y <= y_2 counting as "greater" than all values of y >= y_1 (and using normal comparisons of y-coordinates in comparing two points that are either both above or both below the gap). Harder question; is this true on an arbitrary Riemanian manifold? There can sometimes be infinitely many "shortest paths" between two points, (such as connecting the poles of a sphere, but we just require that the path drawn be any one of the shortest geodesics connecting the pair of points. Andy
(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. If their distance is √(1/2) then there are four such segments.)
—Dan _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com
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.)
You are of course right, Maximilian. Thanks for pointing that out. —Dan
On Tuesday/5January/2021, at 2:56 PM, M F Hasler <mhasler@dsi972.fr> wrote:
I wrote: (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
participants (3)
-
Andy Latto -
Dan Asimov -
M F Hasler