Midpoint lattice polygons - MathOverflow

Midpoint lattice polygons

2012-06-29T12:56:40Z

Midpoint polygons (a.k.a Kasner polygons) have been studied, and their behavior is well understood. I am considering a variant, which I call midpoint lattice polygons. Start with a sequence of distinct points $P=P^0$ drawn from $\mathbb{N}^2$. Define the midpoint of two points $a=(a_x,a_y)$ and $b=(b_x,b_y)$ to be the point with coordinates

$$( \; \lfloor ( a_x + b_x ) / 2 \rfloor, \lfloor ( a_y + b_y ) / 2 \rfloor \; ). $$ Define $P^{k+1} =P^k \cup ($midpoints of $P^k )$ [strike that! instead:] $P^{k+1} =($midpoints of $P^k )$ ~~where by this notation I mean that the midpoints are interleaved between the points of $P^k$,~~ and then all duplicate points are removed to form $P^{k+1}$. Thus, as $k$ increases, $|P_k|$ eventually reduces, I believe always down to a single point $p^*$. Here are two examples, with $P^0$ the 20-point purple scribble, and the last point marked in blue:

I would like to predict two aspects of this process, given $P^0$:

(1) The number of iterations to reach the final point $p^*$.

(2) The coordinates of $p^*$.

In the right example above, it took 39 iterations to reach $p^* = (20,7)$. I had expected the number of iterations would be related to $\log_2 d_{max}$ where $d_{max}$ is the largest coordinate difference between two adjacent points of $P^0$, but that is completely wrong (in this example, $d_{max}=45$). I am having difficulty analyzing this process. Any ideas or literature pointers would be appreciated!

The same questions could be posed for points drawn from $\mathbb{N}^d$ for arbitrary $d$. As the coordinate computations are independent, a key is understanding $d=1$.

Update. Prompted by Barry's question, I realize now (sorry!!!) I misdescribed the process: $P^{k+1} = ($midpoints of $P^k )$, not interleaved with $P^k$, but replacing $P^k$. Here is a simple example, $n=4$ (now, I hope, corrected): $$P^0 = (\; (5,7),(6,9),(6,3),(6,2) \;),$$ $$P^1 = (\; (5,8),(6,6),(6,2),(5,4) \;),$$ $$P^2 = (\; (5,7),(6,4),(5,3),(5,6) \;),$$ $$P^3 = (\; (5,5),(5,3),(5,4),(5,6) \;),$$ $$P^4 = (\; (5,4),(5,3),(5,5) \;),$$ $$P^5 = (\; (5,3),(5,4) \;),$$ $$P^6 = (\; (5,3) \;).$$

Answer by Joseph O'Rourke for Midpoint lattice polygons

2012-07-01T19:37:22Z

It seems my question is not straightforward even for points on a line. If the points are sorted (left below), there is considerable regularity which might lead to prediction. But if the same points are not sorted (right below), the process seems less predictable. And it is this latter situation that is most relevant for 2D lattice polygons.

Answer by Will Sawin for Midpoint lattice polygons

2012-07-29T22:01:08Z

One estimate for the amount of time it takes comes from the continuous analogue. The reasoning is that the discrete and continuous analogues do not differ much until the size is small relative to the number of lattice points, and when that occurs the amount of time until collapse is bounded as a function of the number of lattice points.

The continuous analogue is just the repeated application of a certain matrix to the vector of $x$ and $y$ coordinates. That matrix's highest eigenvalue has norm $\cos \pi/n$, where $n$ is the number of points, so this gives an estimate of

$\frac{ -\ln d}{\ln \cos \pi/n} + O_n(1)$

where $d$ is the max of the difference between the highest $x$ coordinate and the lowest and the highest $y$ coordinate and the lowest.

If we are instead concerned with bounds in terms of $d$, regardless of $n$ then we have the trivial volume-based bound. Consider at each step the convex hull of the lattice points and the point $(x_{min},y_{min})$. It is easy to see that this area must not increase at each step. Moreover, it must decrease, because any corner of the polygon towards the top-right in a given step must be lost in the next step. Thus, the area of the lattice, or $d^2$, is an upper bound on the time.

I suspect that this is not effective and the correct upper bound is linear in $d$. The polygon consisting of all the lattice points in an $a\times b$ rectangle takes $a+b$ steps to collapse, but it is not clear if this is the worst case.