Anchor sets for lattice polygons: Part I

Question

Suppose $V=\{(x_1,y_1), (x_2,y_2),\dots,(x_v,y_v)\}$ is a vertex set of lattice points satisfying $$0=x_1<x_2<\dots<x_v \qquad \text{and} \qquad y_1>y_2>\cdots>y_{v-1}>y_v=0.$$ Construct the polygonal region $D\subset\Bbb{R}^2$ with boundary $\partial D$ along the closed path $$(0,0)\rightarrow (x_1,y_1)\rightarrow(x_2,y_2)\rightarrow\cdots(x_{v-1},y_{v-1})\rightarrow(x_v,y_v)\rightarrow(0,0).$$ Assume $\mathcal{D}=\mathbb{R}_{\geq0}^2-D$ is a convex domain.

QUESTION. Can you determine the smallest positive integer $\ell$ and a finite set $S\subset\mathbb{Z}_{\geq0}^2$ of lattice points containing $V$ such that each of the lattice points $(x,y)\in\mathcal{D}$ can be reached from $(x_j,y_j)\in S$ after performing a lattice-path-move $N$ (north bound) and/or $E$ (east bound), for some $j\in\{1,2,\dots,\vert S\vert\}$; that is, if $[s]=\{1,2,\dots,s\}$ and $s=\vert S\vert$, then $$(x,y)\in\mathcal{D} \qquad \Longrightarrow \qquad \exists a,b\in\Bbb{Z}_{\geq0},\,\, \exists j\in[s]: (x_j+a,y_j+b)=(x,y)\,\,?$$

Answer 1

Consider the set $S_0$ consisting of all points $(x,y)$ such that $(x,y)\in \mathcal D$ but $(x-1,y)$ and $(x,y-1)$ are not in $\mathcal D$. It is clear that $S_0$ satisfies the conditions in the problem and that for any other $S$ satisfying the conditions of the problem we must have $S_0\subseteq S$. Therefore $\ell=|S_0|$. (You can think of $S_0$ as representing the minimal set of monomials generating the corresponding monomial ideal.)

It remains to explicitly describe the elements of $S_0$, and thus give a formula for $\ell$.

For each $1\le i\le v-1$ let's denote by $m_i=\frac{y_{i}-y_{i+1}}{x_{i+1}-x_i}$. Each of the following is easy to check:

• If $m_i\geq 1$ then for each $x_i<x\le x_{i+1}$, the point $(x,\lfloor1+ y_i-m_i(x-x_i)\rfloor)\in S_0$
• If $m_i\le 1$ then for each $y_{i+1}<y\le y_i$, the point $(\lfloor 1 + x_i+m_i^{-1}(y_i-y)\rfloor,y)\in S_0$
• The points $(x_1,1+y_1)$ and $(1+x_v,y_v)$ are in $S_0$
• All the points in $\mathcal D$ can be reached by an NE path from one of these points, therefore there are no other points in $S_0$

By counting over all the cases we get $$\ell=|S_0|=2+\sum_{i=1}^{v-1}\min\{x_{i+1}-x_i, y_i-y_{i+1}\}.$$