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!

Improve this question
$\endgroup$
6
  • $\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
    Commented Nov 2, 2017 at 23:01
  • $\begingroup$ @AnthonyQuas Thanks a lot for the quick reply. Could you please specify a bit more? $\endgroup$
    – user111097
    Commented Nov 2, 2017 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$
    – user111097
    Commented Nov 2, 2017 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
    Commented Nov 2, 2017 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
    Commented Nov 3, 2017 at 1:39

2 Answers 2

Reset to default
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.

Improve this answer
$\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!

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .