1
$\begingroup$

Let $K=[0,1]^2$ be a square and $p\in (0,1)$ be a fixed number. We define a map $F: K^2\to K^2$ as follows.

For $(x_1,y_1), (x_2,y_2)\in K$, it follows by a straightforward computation that there exists a (unique) $\omega\in\mathbb R$ s.t. $\mathcal Les\big(\{(x,y)\in K:~ L_w(x,y)~\le~ 0\}\big)=p$, where $\mathcal Les$ denotes the Lebesgue measure and $L_w$ is defined by

$$L_w(x,y):=(x_2-x_1)\left(x-\frac{x_1+x_2}{2}\right)+(y_2-y_1)\left(x-\frac{y_1+y_2}{2}\right)+\omega.$$

Let $(x_1',y_1')$ and $(x_2',y_2')$ be respectively the centroids (barycentres) of $\{(x,y)\in K:~ L_w(x,y)~\le~ 0\}$ and $\{(x,y)\in K:~ L_w(x,y)~\ge~ 0\}$. Then define the map by

$$F\big((x_1,y_1),(x_2,y_2)\big):=\big((x_1',y_1'),(x_2',y_2')\big).$$

enter image description here

Then of course $F$ has a fixed point. My question is the following: Take an arbitrary $\big((x_1^0,y_1^0),(x_2^0,y_2^0)\big)\in K^2$, and construct the sequence by iteration $\big((x_1^{n+1},y_1^{n+1}),(x_2^{n+1},y_2^{n+1})\big)=F\big((x_1^n,y_1^n),(x_2^n,y_2^n)\big)$. Is this sequence convergent?

Any reply, remark and comment are highly appreciated! Thanks a lot!

$\endgroup$
  • $\begingroup$ In the case where p=1/2, this is a one-dimensional problem: the line separating the barycentres always goes through (1/2,1/2). Have you studied convergence or otherwise in this setting? $\endgroup$ – Anthony Quas Nov 2 '17 at 23:01
  • $\begingroup$ @AnthonyQuas Thanks a lot for the quick reply. Could you please specify a bit more? $\endgroup$ – MB2009 Nov 2 '17 at 23:33
  • $\begingroup$ @AnthonyQuas Actually, this problem is linked to the Voronoi diagram that is used in solving an (semi-discrete) optimal transport problem, where the marginal distributions are given by $\mu=p\delta_{(x_1,y_1)}+(1-p)\delta_{(x_2,y_2)}$ and $\nu=\mathcal{Les}$ $\endgroup$ – MB2009 Nov 2 '17 at 23:35
  • $\begingroup$ Any half-plane whose intersection with the square has measure 1/2 goes through the centre of the square (proof: rotate by 180 degrees around the centre of the square). This means that after step 1, the two pieces are completely defined by the slope of the line joining them. I will rewrite the square as $[-1/2,1/2]^2$. If the slope is $|\epsilon|<1$, I claim the barycentres of the pieces are at $\pm(-\epsilon/6,1/4-\epsilon^2/12)$. If my calcs are right, this shows the new slope is $2\epsilon/(3-\epsilon^2)$. So the slopes $\epsilon=\pm1$ are unstable fixpts; and $\epsilon=0$ is attracting. $\endgroup$ – Anthony Quas Nov 2 '17 at 23:49
  • $\begingroup$ It occurs to me that even for $p\ne1/2$, the subdivision is still determined by the slope, so this remains a one-dimensional problem (and the map is piecewise rational). It should be straightforward enough to answer your question then. $\endgroup$ – Anthony Quas Nov 3 '17 at 1:39
2
$\begingroup$

My suggestion is that you should think of this as a one-dimensional problem. You can parameterize everything by the direction of the vector joining $(x_1,y_1)$ and $(x_2,y_2)$. Given this direction, there is a unique division of the square into regions of area $p$ and $1-p$ with boundary perpendicular to the direction vector (the coordinates of the regions are given by a piecewise function of the slope with square root and linear terms). Now the new barycentres can be computed (again, these are piecewise functions of the original slope involving square roots); and the new slope can be found. The problem is now reduced to an iteration of a one-dimensional dynamical system. You can think of the state space as a circle (the collection of directions for the vector). The map then sends the circle to itself. I suspect it is a homeomorphism of the circle, but I haven't checked this (this is correct in the case $p=\frac 12$). The map also has fixed points when the direction vector is aligned with the axes or is at 45$^\circ$ to the axes. Hence if it is a homeomorphism of the circle, each point converges under iteration to a fixed point (as all orientation-preserving homeomorphisms of the circle with a fixed point have this property).

You asked why I considered only slopes less than 1. You can assume this by rotating the picture, so this is without loss of generality.

$\endgroup$
0
$\begingroup$

Thank @AnthonyQuas for the reply. I claim that this is not an answer, but just a question related to the last remark by @AnthonyQuas

Consider one case where $\Delta x:=x_2-x_1>0$, $\Delta y:=y_2-y_1>0$ and $\Delta x<\Delta y$. Denote further $\bar x:=(x_1+x_2)/2$, $\bar y:=(y_1+y_2)/2$ and

$$V(\omega):=\Big\{(x,y)\in K:\quad L_{\omega}(x,y)~\le~ 0\Big\}.$$

Then one can compute easily the area of $V(\omega)$ by

  1. $\mathcal{Les}\big[V(\omega)\big]=0$ if $\omega\ge 2(\Delta x\bar x+\Delta y\bar y)$
  2. $\mathcal{Les}\big[V(\omega)\big]=(\Delta x\bar x+\Delta y\bar y-\omega/2)^2/2\Delta x\Delta y$ if $2\big(\Delta x(\bar x-1)+\Delta y\bar y\big)\le \omega< 2(\Delta x\bar x+\Delta y\bar y)$
  3. $\mathcal{Les}\big[V(\omega)\big]=(\Delta x\bar x+\Delta y\bar y-\omega/2-\Delta x/2)/\Delta y$ if $2\big(\Delta x\bar x+\Delta y(\bar y-1)\big)\le \omega< 2\big(\Delta x(\bar x-1)+\Delta y\bar y\big)$
  4. $\mathcal{Les}\big[V(\omega)\big]=1-\big(\Delta x(1-\bar x)+\Delta y(1-\bar y)+\omega/2\big)^2/2\Delta x\Delta y$ if $2\big(\Delta x(\bar x-1)+\Delta y(\bar y-1)\big)\le \omega< 2\big(\Delta x\bar x+\Delta y(\bar y-1)\big)$
  5. $\mathcal{Les}\big[V(\omega)\big]=1$ if $\omega<2\big(\Delta x(\bar x-1)+\Delta y(\bar y-1)\big)$

enter image description here

If I understand well the last remark, do you mean the barycentres of $V(\omega)$ and $K-V(\omega)$ are easy to compute? I can't show this map $F$ (defined in my previous question) is contracting. Thank you very much for the reply!

$\endgroup$

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.