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) \;).$$

allinstances of a duplicated point are removed (otherwise $|P_k|$ could only stabilize, never decrease.) Furthermore, it is only adjacent identical points which are removed. Otherwise the set (0,0),(2,3),(1,0),(2,2) would be augmented by four (or maybe three) instances of (1,1) which would instantly be removed leaving no change.Finally, you no doubt require that $P^0$ is a sequence ofdistinctpoints. $\endgroup$ – Aaron Meyerowitz Jun 29 '12 at 23:28replacedby the midpoints, not interleaved (an earlier experiment). Sorry for the confusion; apologies to Gerhard, Barry, and Aaron. :-/ $\endgroup$ – Joseph O'Rourke Jun 29 '12 at 23:44thathappens, each $P^{k+1}$ is exactly the midpoint polygon of $P^k$, so it converges to some $p^*$ (by the linear-algebra exercise I suggested before). Being a lattice polygon, some $P^N$ must collapse to $p^*$,QED. $\endgroup$ – Noam D. Elkies Jun 30 '12 at 5:585more comments