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