Problem on diagonals in a polygon

Question

Consider the polygon $P$ in the following picture which has sides drawn in black and internal diagonals drawn in red and blue. $P$ has 4 convex angles and 4 concave angles in alternating order as it's clear from the picture.

I'm trying to understand if it is possible to shorten one or more sides or blue diagonals of $P$ in a continuous process in such a way that both the following conditions are satisfied:

• by shortening said sides or blue diagonals of $P$ no other side or blue diagonal of $P$ gets longer

• by shortening said sides or blue diagonals of $P$ the lengths the two red diagonals remain constant

All my attempts at doing so failed, so I guess the answer is no, but I can't produce a proof.

Answer 1

The short answer is: We can't make another polygon like that, and I have too much free time on my hands. The slightly longer answer is that we can take the derivative of a function from points to distances. Using linear programming, we show that we can't have all the partial distances be non-positive, which means the can't be all non-increasing; this is exactly the condition that no side or blue diagonal may get longer.

---

Let $P$ be a polygon defined by this ordered list of points $A, a, B, b, C, c, D, d$. Upper-case-letter points are the "outer" points, lower-case-letter points are the "inner" points.

Suppose we map eight arbitrary two-coordinate points to the sixteen distances of the sides and diagonals. (I will be ignoring those eight diagonals between outer and non-contiguous inner points, because we're able to solve this problem without them.) Let $\mu$ be our distance function $\mu : \mathbb{R}^{16} \to \mathbb{R}^{16}$, such that:

• $\mu_1$: Distance from $A$ to $C$.
• $\mu_2$: Distance from $B$ to $D$.
• $\mu_3$: Distance from $A$ to $a$.
• $\mu_4$: Distance from $a$ to $B$.
• $\mu_5$: Distance from $B$ to $b$.
• $\mu_6$: Distance from $b$ to $C$.
• $\mu_7$: Distance from $C$ to $c$.
• $\mu_8$: Distance from $c$ to $D$.
• $\mu_9$: Distance from $D$ to $d$.
• $\mu_{10}$: Distance from $d$ to $A$.
• $\mu_{11}$: Distance from $a$ to $c$.
• $\mu_{12}$: Distance from $b$ to $d$.
• $\mu_{13}$: Distance from $a$ to $b$.
• $\mu_{14}$: Distance from $a$ to $d$.
• $\mu_{15}$: Distance from $b$ to $c$.
• $\mu_{16}$: Distance from $c$ to $d$.

Here are the constant cross-diagonals and side distances.

And here are the inner-point diagonals that we are modeling.

Derive the equation, and you get the Jacobian. We're gonna look at the derivative, but divided, since we only care about positive and negative derivative. It'll also make life easier when we go to solve this thing.

$$D\mu/2 = \left[\frac{\partial \mu}{\partial A_x}\ \frac{\partial \mu}{\partial A_y}\frac{\partial \mu}{\partial a_x}\ \frac{\partial \mu}{\partial a_y} \cdots \frac{\partial \mu}{\partial d_x}\ \frac{\partial \mu}{\partial d_y}\right]$$

Each of those $\partial\mu$ derivatives is actually a column.

For the sake of a proper derivative, I'm going to insert a variable $t$; you can intuitively think of this as time if you want, and the polygon like it's sorta moving. Whatever. It's just there to make things more formal. We want $\frac{\partial \mu_i}{\partial t},$ dependent on some "movement derivatives" $\frac{\partial Point_c}{\partial t}$, like we're moving the point around. We get to choose the movement derivatives, and our goal is to choose them so that the distances either stay equal or decrease as we move our points. From the derivative equation, we know that:

$$\frac{\partial \mu_i}{\partial t} = \frac{\partial \mu_i}{\partial A_x}\frac{\partial A_x}{\partial t} + \cdots \frac{\partial \mu_i}{\partial d_y}\frac{\partial d_y}{\partial t}$$

So it's really like multiplying our matrix by a variable vector. Turns out, the matrix is pretty sparse.

What does each of these listings look like? For instance, in $\mu_1$, we get this equation:

$$\frac{\partial \mu_1}{\partial t} = (A_x - C_x)\frac{\partial A_x}{\partial t} + (A_y - C_y)\frac{\partial A_y}{\partial t} + (C_x - A_x)\frac{\partial C_x}{\partial t} + (C_y - A_y)\frac{\partial C_y}{\partial t}$$

---

At this point, I think it's a good idea to define our particular polygon. I found that these points describe the polygon well: $[(29, 51), (44, 127) (0, 218) ,(86, 185) ,(197, 282 ),(170, 169),(212, 0),(113, 59)]$. Remember, these are for the points $A, a, B, b, C, c, D, d$. I have a link below to plot this polygon, and you can check that it correctly "looks like" the original polygon in this problem, or is at least some acceptable approximation.

Given these polygon points, we can substitute actual numbers in the derivative now. Then we get:

$$\frac{\partial \mu_1}{\partial t} = -168\frac{\partial A_x}{\partial t} -231\frac{\partial A_y}{\partial t} + 168\frac{\partial C_x}{\partial t} + 231\frac{\partial C_y}{\partial t}$$

Hey, this looks like a linear equation! In that case, let Ax stand for $\frac{\partial A_x}{\partial t}$ in the following code listing.

max: Ax - ax + Ay - ay + Bx - bx + By - by + Cx - cx + Cy - cy + Dx - dx + Dy - dy;

r_Ax: Ax = 0;
r_Ay: Ay = 0;
r_Cx: Cx = 0;
r_Cy: Cy = 0;
r_1: -168 Ax -231 Ay +168 Cx +231 Cy = 0;
r_2: -212 Bx +218 By +212 Dx -218 Dy = 0;
r_3: -15 Ax -76 Ay +15 ax +76 ay <= 0;
r_4: +44 ax -91 ay -44 Bx +91 By <= 0;
r_5: -86 Bx +33 By +86 bx -33 by <= 0;
r_6: -111 bx -97 by +111 Cx +97 Cy <= 0;
r_7: +27 Cx +113 Cy -27 cx -113 cy <= 0;
r_8: -42 cx +169 cy +42 Dx -169 Dy <= 0;
r_9: +99 Dx -59 Dy -99 dx +59 dy <= 0;
r_10: +84 dx +8 dy -84 Ax -8 Ay <= 0;
r_11: -126 ax -42 ay +126 cx +42 cy <= 0;
r_12: -27 bx +126 by +27 dx -126 dy <= 0;
r_13: -42 ax -58 ay +42 bx +58 by <= 0;
r_14: -69 ax +68 ay +69 dx -68 dy <= 0;
r_15: -84 bx +16 by +84 cx -16 cy <= 0;
r_16: +57 cx +110 cy -57 dx -110 dy <= 0;
free Ax, Ay, Bx, By, Cx, Cy, Dx, Dy, ax, ay, bx, by, cx, cy, dx, dy;

This is the LP File format for the system of linear equalities that we're trying to solve. A couple things to note here:

• Why are the derivatives for the points $A$ and $C$ set to $0$? When I was running the lp_solver, I noticed it tended to give solutions that were just the original polygon, but translated or rotated. Without loss of generality, we can fix one of the constant diagonals in place. I chose the $AC$ diagonal.
• Why are the other equations equal to zero? Constant derivative means the equation doesn't move. We wanted to keep those diagonals constant, so we set those derivatives to zero.
• What about the other inequalities? We wanted non-increasing distances, whether they were sides or diagonals. That means their derivatives should be less than or equal to zero.
• Why is everything listed as free at the bottom? In the lp_solver program, variables not listed as free will take on non-negative values. Conversely, free variables take on all possible real values, including negative values. You can read more here.

Using the lp_solver program, punch that file in as input. You'll get zero for everything; none of the points can move. Replace the objective function with max: bx or min: bx. You'll get zero, meaning that zero is the only solution. In other words, if you try any other points, you'll break one of our linear programming constraints.

---

Suppose we only took the first twelve distance equations, that is, only the cross diagonals for the inner points. In that case, we do get a solution. It's unbounded, so take an inequality like this:

r_100: Ax - ax + Ay - ay + Bx - bx + By - by + Cx - cx + Cy - cy + Dx - dx + Dy - dy <= 50;

and append it at the end of the lp file listing. When we run the lp_solver program, we get a solution vector for our partial derivatives, which when added to the original points produces this sequence of points: $[(29, 51),(41.71038, 127.451899),(14.5611, 226.59952),(93.82524, 176.04534),(197, 282),(167.6759, 169.555315),(221.24608, 3.43074),(113.992273, 48.5811)]$. Compare that shape with our original shape by going here. Copy/paste the text below and click "Load" to see the shapes. The new shape is on the left in red, the old shape is on the right in yellow.

{ "position": "0 0",
  "model": { "class": "go.GraphLinksModel",
  "nodeDataArray": [ 
{"fill":"yellow", "stroke":"blue", "strokeWidth":3, "category":"PolygonDrawing", "key":-2, "geo":"F M29 51 L44 127 L0 218 L86 185 L197 282 L170 169 L212 0 L113 59z", "loc":"532.25 247.25"},
{"fill":"red", "stroke":"green", "strokeWidth":3, "loc":"226 188", "category":"PolygonDrawing", "geo":"F M29 51 L41.71038 127.451899 L14.5611 226.59952 L93.82524 176.04534 L197 282 L167.6759 169.555315 L221.24608 3.43074 L113.992273 48.5811z", "key":-1}
 ],
  "linkDataArray": []} }

I've taken the coordinates and compared the difference between the distances for the two. Turns out, it's not exactly correct; it deviates from the original polygon by about three units. The largest deviations are between $a$ and $B$ (distance $101.0791769$ units in the original, compared with $102.7975396$ in the new one) and $B$ and $b$ (distance $92.11405973$ in the original polygon, compared with $94.01345119$ in the new one). I would chalk this up to numerical stability problems.

---

A couple questions remain:

• What if I want to try a different polygon? It's very simple. You can substitute the difference in the points' coordinates for any set of point coordinates. Then run any linear programming solver you like, and see what pops out. I would guess, for this configuration, it will probably be zero regardless of the objective function.
• Can you solve this for a generic polygon that "looks like" the one in the statement? The question asks to solve for this polygon $P$, not necessarily for any polygon $P$ that looks like it. Then again, giving a particular instance and solving it is not really in the spirit of the question. What can we do to make the sixteen point coordinates into free variables? The best I've come up with, for now, is considering all the left-of relations. Given three points $A, B, C$, the point $C$ is left of the line $AB$ if $A_xB_y + B_xC_y + C_xA_y - A_xC_y - C_xB_y - B_xA_y < 0$. Unfortunately, that's not a linear inequality.

Answer 2

This a classical engineering problem, that falls under the subject of Static Analysis of Trusses, as well as under that of Kinematic Chains. You are probably not familiar with such discipline, and there is no space here to resume its basis.
However, since everybody has common experience of trusses and kinematic chains, I will cite here some facts that should sound "plausible", while referencing to specialized documentation for a rigourous treatment.

The figure above translates the problem you proposed in the engineering language.

The black and red segments are stiff rods (elements) and the circles represents pin joints (nodes).
Being stiff, all the elements are supposed not to change in length, and can only rotate around the joints. Note that at the points where the diagonal elements cross there is no bound, meaning that the elements can freely slide over each other.

Now, a rigid body in the plane has three degre of freedom to move: two for translation and one for rotation.
To null them and "keep the truss on the drawing sheet" it is customary to fix the $(x,y)$ position of one node (here $A$) and give another (suitably chosed) only the fredom to move horizontally (here $C$). In this way the whole truss can only have "internal" movements and not "as a whole".

One of the major scopes of the Static Analysis is to determine infact if the truss can have or not such "internal movements". If it has, it will be unstable, and under a minimal load it will collapse, in the sense
that it will change its shape macroscopically. If it has not, then it may be Isostatic or OverConstrained.
And this distinction is very important in Construction Design.

Your question practically translates to ask whether the truss is underconstrained or not.

A result of Static Analysis, well known to all engineers, says that a necessary condition for the system
to be underconstrained is that
$$ m < 2n - 3 $$
(if $m=2n-3$ it is isostatic, and overdetermined if $m>2n-3$)
where $m$ is the number of elements and $n$ the numbers of nodes (pin joints).
The results comes from analyzing the degrees of freedom of the various members and the degrees
reduced by the constraints.

Your "truss" gives $m=10<2n-3=13$, and so it is heavily undetermined, having $3$ degrees of freedom
unrestrained.
Thus it can move without changing the length of any member, and since shortening consumes 1 degree
of movement, sure you can short any segment even without changing the length of the other $9$.
Clearly, the amount of movement or shortening is limited to a certain extent.

The picture below provides an example

--- Addendum ----

Finally, after the clearing got from the comments and the re-editing of the post, the truss has become highly Hyperstatic. To solve the problem in this case we can refer to a truss whose members are stiff vs. elongation and soft vs. compression, except only the diagonals $AE$ and $GC$ which are stiff in both directions. A sort of a truss made by wires around the two main diagonal rods.

If such a truss turns out to be stable, then it means that you cannot shorten a side without stretching some other.

But now the truss is quite complicated to be solved "by hand", and its non-linear stiffness complicates the analysis (a director's chair is not a proper truss).

If we move the sliding bound to $E$, we get a vertical stiff rod ($GC$) connected at both ends by wires stranding from the fix nodes, and these strands are then tightly knotted somewhere in between in all directions (the other connections are not shown to reduce cluttering).
Common experience suggests that it should be sufficient to secure the vertical rod (unless of extreme configurations).
But how to provide mathematical evidence of that is out of my reach, at present.