In the question below, what is the meaning of the brackets in |P-f(P)| ? I thought |P-Q| by default meant the Euclidean distance between the points. From what have I read, that seems to be called l2, not L_\infty. But much of the discussion here seems to be about L_infinity. I am math semi-literate, what am I missing here? It seems to matter below.
Date: Wed, 27 May 2015 23:13:06 -0400 From: "David Wilson"<davidwwilson@comcast.net>
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?
In signal and image processing, the word for bijection is "lossless", and the standard integer-approximation lossless rotation is called the "lifted Givens rotation." The "butterfly" operation within FFTs and DCTs is one application. Expressed as a Python function of x, y, and an angle: def lifted_Givens(x0, y0, theta): x1 = x0 +*round(* y0 * ( cos(theta) - 1 ) / sin(theta)*)* y2 = y0 +*round(* x1 * sin(theta)*)* x2 = x1 +*round(* y2 * ( cos(theta) - 1 ) / sin(theta)*)* return (x2, y2)
Date: Thu, 28 May 2015 18:23:51 +0000 From: Veit Elser <ve10@cornell.edu>
Take a look at this: http://arxiv.org/pdf/1305.1798.pdf
Figure 4 shows such a bijection-generating fundamental domain. The diameter is given in equation (1), which, after you divide by 2, gives the bound 0.92 ? on c (for the L_infinity norm). This is actually a very good bound, considering the fact that 1/sqrt(2) = 0.707 is a lower bound. Exercise: Prove that c >= 1/sqrt(2).
Testing the lifted_Givens() function with random numbers, the largest errors I've seen are Euclidian distance: 0.9237+ (l_2?) Max of x error and y error: 0.8534+ (L_infinity?) Since the greatest Euclidean-distance error I get is close to the number from Eq. 1 in the paper, which Veit says is for the L_infinity norm, and the number I get for what I would think is L_infinity, is noticeably less than that, I am confused here. I'm unfamiliar with fundamental domains, although I have generated fractals from orbits of these rotations. (Set the denominator to 8 for 45 degrees, then press Draw.): http://www.tiac.net/~sw/2005/03/Mandala <http://www.tiac.net/%7Esw/2005/03/Mandala> --Steve p.s. Java applets seem to be working again in the latest Chrome.