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:
    Iterations Image
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) \;).$$
             Midpoints n=4

  • 2
    $\begingroup$ Joseph, I'm confused by your definition of $P^{k+1}$. Could you add another, perhaps smaller example with at least one step spelled out in detail? Also, would it make sense at each step to translate the polygon so that it has a leftmost vertex on the $y$ axis and a bottommost vertex on the $x$ axis? (The coordinate of $p*$ would be recoverable as a running sum of the translations.) $\endgroup$ – Barry Cipra Jun 29 '12 at 19:49
  • 1
    $\begingroup$ If you consider a 1-gon, you will get to all the midpoints in O(log d), where d is the distance between the two initial points. Since Joseph is using floor and removing all duplicates ( and I am doing everything in the first quadrant ) some of the points will disappear before the others. What I don't understand is why points furthest from the origin seem to disappear. Gerhard "Puzzled About Enduring Maximal Points" Paseman, 2012.06.29 $\endgroup$ – Gerhard Paseman Jun 29 '12 at 21:11
  • 1
    $\begingroup$ An example would help. I assume that the interleaving is cyclic. Also that all instances 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 of distinct points. $\endgroup$ – Aaron Meyerowitz Jun 29 '12 at 23:28
  • 1
    $\begingroup$ @Barry: You are absolutely correct (and very gentle not to bash me!). I had misdescribed it: $P^k$ is replaced by 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:44
  • 2
    $\begingroup$ For this lattice problem, existence of $p^*$ can be proved as follows. Let $n_k$ be the number of vertices of $P^k$. Then $\lbrace n_k\rbrace$ is a nonincreasing sequence of positive integers, so it is constant from some point onwards. At that point, let $S_k$ be sum of the $x$- and $y$-coordinates of $P^k$. This is again nonincreasing so again eventually constant. Once that happens, 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:58

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.

  • $\begingroup$ Insightful analysis, Will! One query: $\cos \pi/n$ is less than $1$, so $\ln \cos \pi/n$ is negative... $\endgroup$ – Joseph O'Rourke Jul 29 '12 at 23:57
  • $\begingroup$ I like your question at the end: What is the worst-case lattice polygon, the one that takes the longest to collapse to a point? $\endgroup$ – Joseph O'Rourke Jul 29 '12 at 23:58
  • $\begingroup$ Yeah there should be a minus sign. I think you can improve the bound if you cut off the top right corner and replace it with a diagonal with a step of $2$. That configuration will be more stable, but I'm not sure how much that helps. $\endgroup$ – Will Sawin Jul 30 '12 at 2:19
  • $\begingroup$ Consider all the lattice points in an $a \times b$ rectangle. Let's play a different game. At each step, remove a lattice point if there is no pair of distinct points contained in the previous rectangle which it is the midpoint of. A single point in the top-right corner gets removed in the first step, then the two adjacent points, then just two of the three remaining points, and so on. It is clear that the original rectangle. The number of steps it takes to remove all the lattice points provides an obvious upper bound on the original problem. $\endgroup$ – Will Sawin Jul 30 '12 at 2:27
  • $\begingroup$ 1. What is this bound? 2. At any given time, the removed points approximate a rectangle with the fourth corner smoothed into a curve. Asymptotically, what is this curve? $\endgroup$ – Will Sawin Jul 30 '12 at 2:28

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.
 MidPoints on a Line


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.