Given a convex polygon with integer coordinates vertices, how can you transform it so you can always find a point inside it with integer coordinates?

Question

Given a convex polygon, with all its vertices having integer coordinates, you are allowed to perform one transformation T to all of its vertices (which are points), such that:

• T transforms a point in another (possibly the same) point.
• If P is a point with integer coordinates, T(P) will be a point with integer coordinates.
• Let u, v be two consecutive vertices of the original polygon. If a point P was originally on the edge {u, v} of the original polygon, T(P) will be a point that is on the edge {T(u), T(v)} of the transformed polygon.
• If a point P was originally in the interior of the original polygon, T(P) will be a point that is in the interior of the transformed polygon.
• If a point P was originally outside the original polygon, T(P) will be a point that is outside the transformed polygon.

After applying the transformation T to the polygon, you must find a point Q in the interior the transformed polygon with integer coordinates.

• Notice that Q must not be on an edge of the transformed polygon, but strictly in the interior of it.

You may assume that:

• We are working in 2D.
• No two vertices of the original polygon are the same.
• No three consecutive vertices of the original polygon are collinear.

I'm interested in finding a transformation T that satisfies those conditions for all polygons with vertices with integer coordinates, and a way to generate a point with integer coordinates in the interior of the transformed polygon.

Some observations I've come to, but couldn't prove:

It appears that all convex polygons with integer coordinates vertices such that

1. The maximum Y of any of its points minus the minimum Y of any of its points is 1; or
2. The maximum X of any of its points minus the minimum X of any of its points is 1

will yield no points with integer coordinates in the interior of them.

One particular example is the triangle formed by {0, 0}, {0, 1}, {1, 0}.

Triangle of the example

• For this case, notice that any of the following transformations will still yield a polygon with no integer coordinates points inside of it:

  1. (x, y) -> (2x, y) Transformation 1

  2. (x, y) -> (x, 2y) Transformation 2

  3. (x, y) -> (2x, 2y) Transformation 3

• But the following transformations will:

  1. (x, y) -> (-3x, -3y) Transformation 1A

  2. (x, y) -> (6x, 4y) Transformation 2A

Answer 1

The transformation $T(x,y) = (3x,3y)$ always works.

Here's why. Let $A = (x_0, y_0)$, $B = (x_1, y_1)$, and $C = (x_2, y_2)$ be three vertices of the polygon. Then their centroid $G = (\frac{x_0+x_1+x_2}{3}, \frac{y_0 + y_1 + y_2}{3})$ is in the interior of $\triangle ABC$, and therefore in the interior of the polygon.

The linear transformation has all the nice properties we want, and in particular it preserves interiors. So we know that $T(G)$ is in the interior of the transformed polygon.

But it's also true that $T(G)$ has integer coordinates: more precisely, the integer coordinates $(x_0 + x_1 + x_2, y_0 + y_1 + y_2)$.

---

In fact, as long as the polygon is not a triangle, the transformation $T(x,y) = (2x,2y)$ will work. For this, let $A = (x_0, y_0)$ and $B = (x_1, y_1)$ be two vertices of the polygon that are not adjacent. Then the midpoint of $AB$, the point $M = (\frac{x_0 + x_1}{2}, \frac{y_0 + y_1}{2})$, is in the interior of the polygon, and by a similar argument as for the previous transformation, $T(M) = (x_0 + x_1, y_0 + y_1)$ is an integer point inside the transformed polygon.