Problem on diagonals in a polygon

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.

distances 1 through 10, and points labeled

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

distances 11 through 16, and points labeled

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.

Tags:

Polygons

Euclidean Geometry

Related

Calculating dimension of the intersection of two subspaces If $n$ is any odd number, prove that $\displaystyle{\sum_{k=1}^{n-1}\frac{(n-1)!}{k} \equiv 0 \pmod{n}}$. Is $\mathbb{R}/\mathord{\sim}$ a Hausdorff space if $\{(x,y)\!:x\sim y\}$ is a closed subset of $\mathbb{R}\times\mathbb{R}$? What Is the Difference Between Interior Point Methods, Active Set Methods, Cutting Plane Methods and Proximal Gradient Methods? More `General' Chinese Remainder Theorem How does proof by contradiction work? Upper semicontinuity on a normal space Integral $\int_0^\pi \big( (1+\alpha \cos x) \cos x \big)^n dx $ Distance between Centroids of the Faces of a Regular Tetrahedron Probability of two people meeting in a given square grid. Finding the next term in a sequence. Are there any other interesting topologies on $\mathrm{Spec} (A)$ other than Zariski's?

Recent Posts