Polygon Construction for Specified Number of Interior and Boundary Lattice Points

Question

Construct a simple polygon on a grid of equal-distanced points such that:

1. all the polygon's vertices are grid points,
2. there are exactly $i~(\geq 0)$ lattice points in the interior, and
3. there are exactly $b~(\geq 3)$ lattice points on the boundary.

As a practice, construct it for:

• $i = 5$ and $b = 12$
• $i = 0$ and $b = 10$
• $i = 9$ and $b = 3$

As for examples:

• On the left side, it's a polygon with $5$ interior points and $16$ boundary points.
• On the right side, it's a polygon with $9$ interior points and $10$ boundary points.

---

_{^{This puzzle was submitted (but not accepted) for The 31st International Olympiad in Informatics (IOI 2019).}}

Answer 1

Here is the answer for practice ones:

1:

2:

3:

To construct b=3;

You just need to make a bigger triangle for all i's.

As show below for i=9.

The general idea is actually the same as above, if you want to increase b

you just need to visit extra points for the triangle while controlling your i value.

for example, if you want b=5 and i=9;

or for example, if you want b=20 and i=9;

So you should

decide your $i$ first as a triangle b=3, then increase b as much as you want on the grid to control the value of b.

so you can create polygons with every $i\geq0$ and $b\geq3$ values with the method above.