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