[math-fun] Z^2 scale/rotate/translate puzzle
Here's a puzzle some of you might like: You have a finite set of points in Z^2, so they all have integer coordinates. Taken together, the set of points defines an object. The problem is to find a scale/rotation/translation (with no reflection) that maps those points into Z^2, minimizing the size of the object (i.e. minimizing the distances between pairs of points). Example: Suppose you have the following five points: (-3, 6) (-4, -7) (6, 3) (1, 8) (2, 1) These can be scaled/rotated/translated to: (0, 1) (-4, 0) (0, -2) (1, 0) (-1, -1) This scales the original object by 1/sqrt(10), leaving it in its smallest possible form while preserving its shape. Ignoring translation, any optimal solution may be rotated by multiples of 90 degrees to obtain three additional optimal solutions, for a total of four. This may be a well-known problem, but it was unknown to me. My first thought was to do some sort of exhaustive search, but I ended up finding a much better solution. Any thoughts? Tom
I'm guessing factorization of Gaussian integers is involved... BTW, how come reflection isn't allowed? At 12:51 AM 10/21/2020, Tom Karzes wrote:
Here's a puzzle some of you might like:
You have a finite set of points in Z^2, so they all have integer coordinates. Taken together, the set of points defines an object.
The problem is to find a scale/rotation/translation (with no reflection) that maps those points into Z^2, minimizing the size of the object (i.e. minimizing the distances between pairs of points).
Example: Suppose you have the following five points:
(-3, 6) (-4, -7) (6, 3) (1, 8) (2, 1)
These can be scaled/rotated/translated to:
(0, 1) (-4, 0) (0, -2) (1, 0) (-1, -1)
This scales the original object by 1/sqrt(10), leaving it in its smallest possible form while preserving its shape.
Ignoring translation, any optimal solution may be rotated by multiples of 90 degrees to obtain three additional optimal solutions, for a total of four.
This may be a well-known problem, but it was unknown to me. My first thought was to do some sort of exhaustive search, but I ended up finding a much better solution.
Any thoughts?
Tom
I really just want a single shrunken version of the object. Adding reflection is trivial (just negate x or y), so there's no need to throw reflected solutions into the mix. Once a reference solution is found, the solution set can be quadrupled by rotating by multiples of 90 degrees, and doubled by adding reflection if desired, so there's no reason to use a reflected solution as the reference solution. Tom Henry Baker writes:
I'm guessing factorization of Gaussian integers is involved...
BTW, how come reflection isn't allowed?
At 12:51 AM 10/21/2020, Tom Karzes wrote:
Here's a puzzle some of you might like:
You have a finite set of points in Z^2, so they all have integer coordinates. Taken together, the set of points defines an object.
The problem is to find a scale/rotation/translation (with no reflection) that maps those points into Z^2, minimizing the size of the object (i.e. minimizing the distances between pairs of points).
Example: Suppose you have the following five points:
(-3, 6) (-4, -7) (6, 3) (1, 8) (2, 1)
These can be scaled/rotated/translated to:
(0, 1) (-4, 0) (0, -2) (1, 0) (-1, -1)
This scales the original object by 1/sqrt(10), leaving it in its smallest possible form while preserving its shape.
Ignoring translation, any optimal solution may be rotated by multiples of 90 degrees to obtain three additional optimal solutions, for a total of four.
This may be a well-known problem, but it was unknown to me. My first thought was to do some sort of exhaustive search, but I ended up finding a much better solution.
Any thoughts?
Tom
You can avoid totally exhaustive search by first ignoring all the y-coordinates, and then by ignoring all the x-coordinates. I got this hint by asking what would happen in higher dimensions. Only if you get a *consistent* mapping for both x- and y-coordinates separately, do you check more carefully. Since you already have one consistent mapping, any other mapping is *smaller*, and hence easier to disprove, so the search terminates, and should speed up towards the end. At 12:51 AM 10/21/2020, Tom Karzes wrote:
Here's a puzzle some of you might like:
You have a finite set of points in Z^2, so they all have integer coordinates. Taken together, the set of points defines an object.
The problem is to find a scale/rotation/translation (with no reflection) that maps those points into Z^2, minimizing the size of the object (i.e. minimizing the distances between pairs of points).
Example: Suppose you have the following five points:
(-3, 6) (-4, -7) (6, 3) (1, 8) (2, 1)
These can be scaled/rotated/translated to:
(0, 1) (-4, 0) (0, -2) (1, 0) (-1, -1)
This scales the original object by 1/sqrt(10), leaving it in its smallest possible form while preserving its shape.
Ignoring translation, any optimal solution may be rotated by multiples of 90 degrees to obtain three additional optimal solutions, for a total of four.
This may be a well-known problem, but it was unknown to me. My first thought was to do some sort of exhaustive search, but I ended up finding a much better solution.
Any thoughts?
Tom
participants (2)
-
Henry Baker -
Tom Karzes