Let G1 = Z^2 be the grid of integer points in the plane R^2. Let G2 be the grid of points in R^2 gotten by rotating G1 by 45° about the origin. What is the smallest c for which there exists bijection f: G1óG2 with |P-f(P)| ≤ c for all P?
I looked at bijections like this back in the 1980s, though I never tried to determine the optimum c. As I recall, one nice way to construct such bijections (suggested either by Bill Thurston or Curt McMullen) involved writing the rotation as a product of skew transformations. If two lattices are related by a skew transformation that preserves infinitely many points, then finding a bijection between them that doesn't move points too far reduces to infinitely 1-dimensional matching problems (and matching two 1-dimensional lattices lying on the same line is trivial). I hope that's clear though I fear it's not. Jim Propp On Wednesday, May 27, 2015, David Wilson <davidwwilson@comcast.net> wrote:
Let G1 = Z^2 be the grid of integer points in the plane R^2.
Let G2 be the grid of points in R^2 gotten by rotating G1 by 45° about the origin.
What is the smallest c for which there exists bijection f: G1óG2 with |P-f(P)| ≤ c for all P?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I've worked on a related problem, where instead of minimizing the L_infinity-norm of P - f(P) for bijections f, you minimize the L_2-norm. The nicest way to display the bijection is as a fundamental domain F of both lattices. Centering F on P of one lattice will then contain a unique point f(P) of the other lattice. For the L_2-norm case I got two solutions for F (a fractal), related by a 45-degree rotation. -Veit
On May 27, 2015, at 9:04 PM, James Propp <jamespropp@gmail.com> wrote:
I looked at bijections like this back in the 1980s, though I never tried to determine the optimum c.
As I recall, one nice way to construct such bijections (suggested either by Bill Thurston or Curt McMullen) involved writing the rotation as a product of skew transformations. If two lattices are related by a skew transformation that preserves infinitely many points, then finding a bijection between them that doesn't move points too far reduces to infinitely 1-dimensional matching problems (and matching two 1-dimensional lattices lying on the same line is trivial).
I hope that's clear though I fear it's not.
Jim Propp
On Wednesday, May 27, 2015, David Wilson <davidwwilson@comcast.net> wrote:
Let G1 = Z^2 be the grid of integer points in the plane R^2.
Let G2 be the grid of points in R^2 gotten by rotating G1 by 45° about the origin.
What is the smallest c for which there exists bijection f: G1óG2 with |P-f(P)| ≤ c for all P?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I'd be interested in hearing of any upper bound on c. Can the maximum displacement be, say, 17? How about 17,000? On Thu, May 28, 2015 at 2:28 AM, Veit Elser <ve10@cornell.edu> wrote:
I've worked on a related problem, where instead of minimizing the L_infinity-norm of P - f(P) for bijections f, you minimize the L_2-norm. The nicest way to display the bijection is as a fundamental domain F of both lattices. Centering F on P of one lattice will then contain a unique point f(P) of the other lattice. For the L_2-norm case I got two solutions for F (a fractal), related by a 45-degree rotation.
-Veit
On May 27, 2015, at 9:04 PM, James Propp <jamespropp@gmail.com> wrote:
I looked at bijections like this back in the 1980s, though I never tried to determine the optimum c.
As I recall, one nice way to construct such bijections (suggested either by Bill Thurston or Curt McMullen) involved writing the rotation as a product of skew transformations. If two lattices are related by a skew transformation that preserves infinitely many points, then finding a bijection between them that doesn't move points too far reduces to infinitely 1-dimensional matching problems (and matching two 1-dimensional lattices lying on the same line is trivial).
I hope that's clear though I fear it's not.
Jim Propp
On Wednesday, May 27, 2015, David Wilson <davidwwilson@comcast.net> wrote:
Let G1 = Z^2 be the grid of integer points in the plane R^2.
Let G2 be the grid of points in R^2 gotten by rotating G1 by 45° about the origin.
What is the smallest c for which there exists bijection f: G1óG2 with |P-f(P)| ≤ c for all P?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
There’s a bijection for which the associated fundamental domain has the symmetry of the regular octagon. The circumradius of that domain, sqrt(2+sqrt(2))/2 = 0.92 … , is an upper bound on c. -Veit
On May 28, 2015, at 6:36 AM, Allan Wechsler <acwacw@gmail.com> wrote:
I'd be interested in hearing of any upper bound on c. Can the maximum displacement be, say, 17? How about 17,000?
participants (4)
-
Allan Wechsler -
David Wilson -
James Propp -
Veit Elser