# Reordering vertices of a polygon

Let $Q,Q'$ be two planar polygons with the same number $n>3$ of vertices. There is a correspondence between vertices of $Q$ and $Q'$: to any vertex $z$ of $Q$ corresponds a unique vertex $z'$ of $Q'$. Suppose $Q$ (resp. $Q'$) has strictly convex internal angles only in three vertices $v_1,v_2,v_3$ (resp. $v_1',v_2',v_3'$). Endow each polygon with the intrinsic Euclidean metric (the distance between two points is defined as the infimum of the lengths, computed with respect to the Euclidean metric, of all paths contained in the polygon connecting the two points): denote the metrics respectively $d_Q$ and $d_{Q'}$, given $x,y\in Q$, $\overline{xy}$ is the geodesic for $d_Q$ between $x$ and $y$.

Since $Q$ has exactly three convex internal angles, $\overline{v_1v_2}$ is the portion of $\partial Q$ between $v_1$ and $v_2$ not containing $v_3$.

Suppose that the order of the vertices of $Q$ with concave internal angle is different from the order of the vertices of $Q'$ with concave internal angle. This means that for any $z,z_1,z_2$ vertices of $Q$ it can happen:

• $z\in \overline{v_iv_j}$ and $z'\in \overline{v_j'v_k'}$
• $z_1,z_2\in \overline{v_iv_j}$, $z_1',z_2'\in \overline{v_i'v_j'}$, $d_{Q}(v_i,z_1)<d_Q(v_i,z_2)$, $d_{Q'}(v_i',z_2')<d_{Q'}(v_i',z_1')$

Finally, suppose that the distance with respect to $d_Q$ between any two vertices of $Q$ is greater or equal to the distance with respect to $d_{Q'}$ between the two corresponding vertices of $Q'$.

For every such $Q,Q'$ I want to find a third polygon $Q''$ entirely contained in $Q'$ such that:

• to every vertex $z$ of $Q$ corresponds a vertex $z''$ of $Q''$ and furthermore it results $v_i''=v_i'$, $i=1,2,3$. This means that $Q''$ can have more than $n$ vertices, with the condition that the internal angle at vertices which do not correspond to vertices of $Q$ must be concave

• vertices of $Q$ have the same order of the corresponding vertices of $Q''$

• the distance with respect to $d_Q$ between any two vertices of $Q$ is greater or equal to the distance with respect to $d_{Q''}$ between the two corresponding vertices of $Q''$

I am having great difficulties proving the existence of $Q''$ because it seems to me that it can not be obtained moving one vertex of $Q'$ at a time. For example, if $z\in \overline{v_iv_j}$ and $z'\in \overline{v_j'v_k'}$ and one tries to move $z'$ to place it on $\overline{v_j'v_k'}$, then $d_{Q'}(z',z_1')$ ($z_1'$ is any vertex of $Q'$) might become equal to $d_{Q}(z,z_1)$ before $z'$ reaches $\overline{v_j'v_k'}$. If one then tries to move $z_1'$ then $d_{Q'}(z_1',z_2')$ ($z_2'$ is another vertex of $Q'$) might become equal to $d_{Q}(z_1,z_2)$ before $z_1'$ is moved enough to let $z'$ reach $\overline{v_i'v_j'}$.

Can you think of a better way to obtain $Q''$?

• Do you mean $\ \forall_{Q\ Q'}\$ (etc.) or $\ \exists_{Q\ Q'}\$ (etc.) ? – Wlod AA Jun 1 '18 at 22:00
• To check my understanding, $Q,Q'$ are pseudotriangles en.wikipedia.org/wiki/Pseudotriangle . I do not understand the first bullet point in your conditions on $Q''$: "there is a correspondence between vertices of $Q$ and $Q''$ and it results $v_i''=v_i'$ "? Does the first part just amount to the condition that $Q''$ must have $n$ vertices? – j.c. Jun 2 '18 at 3:48
• @WlodAA I want to prove that for every $Q$ and $Q'$ there is a $Q''$ – user101163 Jun 2 '18 at 8:05
• @j.c. Yes, $Q,Q'$ are pseudotriangles. I am sorry, the point you cited was not clear, I hope it is clear now. I also means that $v_i',i=1,2,3$ must be vertices of $Q''$ – user101163 Jun 2 '18 at 8:41
• Thank you for your kind answer. This is a nice question. – Wlod AA Jun 3 '18 at 4:11

I'm not certain, but it may be that the expansive motions in the Connelly-Demaine-Rote paper cited below can provide a route to your $Q''$. An expansive motion is one in which the distance between every pair of vertices increases or stays the same. Here is an example of a convexifying expansive motion:
• Thank you for your answer, but I don't see how the result you cite could be applied to my case. Vertices of polygons $Q$ and $Q'$ can have different order in the sense that if $\overline{xy}$ is a side of $Q$ then $\overline{x'y'}$ can be a diagonal of $Q'$. I am searching for another polygon $Q''$ entirely contained in $Q'$ and which shares with it three vertices $v_i'=v_i''$, $i=1,2,3$ (the ones of $Q'$ with strictly convex internal angles). – user101163 May 31 '18 at 8:15
• The distance between some pair of vertices of $Q''$ can be greater than the distance between corresponding vertices of $Q'$, but not greater than the corresponding vertices of $Q$. I am not trying to expand $Q'$ in order to make it convex, but rather to move its vertices inside $Q'$ (fixing three $v_i'$) in order to reorder them – user101163 May 31 '18 at 8:18
• @user389604: Apologies for not understanding your question. I thought the correspondence between $Q$ and $Q'$ implied the same ordering of their vertices. – Joseph O'Rourke May 31 '18 at 11:05