Reordering vertices of a polygon

Question

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''$?

Answer 1

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:

---

         

---

They proved that there always exists an expansive motion for a nonconvex polygon. It remains simple (non-self-intersecting) throughout the motion. The above example was a difficult case that we thought might be "locked"; but it is not.

Robert Connelly, Erik D. Demaine, and Günter Rote, “Straightening Polygonal Arcs and Convexifying Polygonal Cycles,” Discrete & Computational Geometry, volume 30, number 2, September 2003, pages 205–239. (Author link.)