Is the area of a polygonal linkage maximized by having all vertices on a circle? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T06:15:00Z http://mathoverflow.net/feeds/question/22767 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/22767/is-the-area-of-a-polygonal-linkage-maximized-by-having-all-vertices-on-a-circle Is the area of a polygonal linkage maximized by having all vertices on a circle? Greg Muller 2010-04-27T19:36:01Z 2010-04-28T15:13:50Z <p>Consider a (non-stellated) polygon in the plane. Imagine that the edges are rigid, but that the vertices consist of flexible joints. That is, one is allowed to move the polygon around in such a way that the vertices stay a fixed distance from their adjacent neighbors. Such a system is called a <strong>polygonal linkage</strong>. </p> <p>As the linkage varies in its embedding in the plane, the area of the interior varies. The question is, <strong>When is the area maximized</strong>?</p> <p>I have a specific answer I suspect is correct, but I am having trouble showing. I believe it is true that every polygonal linkage has as embedding where all the vertices lie on one circle (this isn't hard to show in the case when the linkage starts non-stellated). My claim is that <strong>the area is maximized exactly when all the vertices lie on a circle</strong>. </p> <p>I can show this for a 4-sided polygon, but with techniques that do not generalize.</p> <p>Also, my requirement that the polygon be non-stellated was only so that it was clear that there <em>was</em> a way to flex it to have all vertices on a circle. This question extends to the stellated case, but the question there is whether every stellated linkage can be flexed to one which is non-stellated.</p> http://mathoverflow.net/questions/22767/is-the-area-of-a-polygonal-linkage-maximized-by-having-all-vertices-on-a-circle/22774#22774 Answer by David Speyer for Is the area of a polygonal linkage maximized by having all vertices on a circle? David Speyer 2010-04-27T20:19:47Z 2010-04-27T20:19:47Z <p>If you can show it for a quadrilateral, then it is true in general. </p> <p><strong>Proof Sketch:</strong> by induction on the number of sides. The base case is $n=4$, which you say you have done. Let $X$ be the set of joints. By a compactness argument, the maximum is achieved; pick a particular placement which achieves the maximum.</p> <p>Consider a new linkage $X'$ with $n-1$ vertices. The distance between <code>$x'_i$</code> and <code>$x'_{i+1}$</code> is the same as that between <code>$x_i$</code> and <code>$x_{i+1}$</code>; the distance between <code>$x'_1$</code> and <code>$x'_{n-1}$</code> is the same as the distance between $x_1$ and $x_{n-1}$ in the chosen optimal placement. Then the chosen placement of the $x_i$'s must also be an optimal placement of the <code>$x'_i$</code>'s; if not, we could keep $(x_1, x_{n-1}, x_n)$ in the same place and move the other $x_j$'s to a better placement for linkage $X'$, obtaining a better placement of $X$.</p> <p>By induction, we see that <code>$\{ x_1, x_2, \ldots, x_{n-1} \}$</code> lie on a circle. But the same applies to any index, so <code>$X \setminus \{ x_i \}$</code> lies on a circle $C_i$ for any $i$. We see that $C_i$ and $C_j$ have $n-2$ points in common so (for $n>4$) they must be the same circle. So all the points lie on a circle.</p> <hr> <p>As regards your other question, as to whether every closed linkage to be unfolded to lie on a circle, I believe the answer is also yes. Let $d_1$, $d_2$, ..., $d_n$ be the lengths of the sides. Without loss of generality, let $d_n = \max(d_i)$. Since your linkage closes, we have <code>$d_n &lt; \sum_{i &lt;n} d_i$</code> by the triangle inequality.</p> <p>Consider the function $f(R) = \sum 2 \sin^{-1}(d_i/(2R))$. When $R=d_n/2$, all the inverse sines are defined, and we have <code>$$f(R) &gt; \pi + 2 \sin^{-1} (\sum_{i&lt;n} d_i/d_n) \geq 2 \pi,$$</code> where we have used the inequality $\sin^{-1}(x) + \sin^{-1}(y) \geq \sin^{-1}(x+y)$, following from the convexity of $\sin^{-1}$.</p> <p>As $R$ goes to infinity, $f(R)$ goes to $0$. By the intermediate value theorem, $f(R)$ is $2 \pi$ somewhere; your linkage can be unfolded onto a circle of this radus $R$. </p> http://mathoverflow.net/questions/22767/is-the-area-of-a-polygonal-linkage-maximized-by-having-all-vertices-on-a-circle/22775#22775 Answer by Gjergji Zaimi for Is the area of a polygonal linkage maximized by having all vertices on a circle? Gjergji Zaimi 2010-04-27T20:26:19Z 2010-04-27T21:37:30Z <p>This is a theorem of Cramer. See <a href="http://www.emis.ams.org/journals/MV/9634/ves96301.ps" rel="nofollow">here</a></p> <p>For the quadrilateral case the quickest proof is using <a href="http://en.wikipedia.org/wiki/Brahmagupta%27s_formula#Extension_to_non-cyclic_quadrilaterals" rel="nofollow"> Brahmagupta's formula</a></p> <p>$$Area=\sqrt{(s-a)(s-b)(s-c)(s-d)-abcd\cos^2 \theta}$$ where $a,b,c,d$ are the sides, $s$ is the half perimeter and $\theta$ is half the sum of opposite angles.</p> <p>Edit: I wonder if this argument works: Pick four consecutive vertices and move the linkage made of these four vertices till it's cyclic. There will be a subsequence of the polygons we get after such operations which converges, by the Weierstrass theorem. In the limit the polygon will be cyclic otherwise you can find four consecutive vertices not on a circle and increase the area again.</p> http://mathoverflow.net/questions/22767/is-the-area-of-a-polygonal-linkage-maximized-by-having-all-vertices-on-a-circle/22776#22776 Answer by Joseph Malkevitch for Is the area of a polygonal linkage maximized by having all vertices on a circle? Joseph Malkevitch 2010-04-27T20:32:24Z 2010-04-27T20:32:24Z <p>A theorem of Connelly, Demaine, and Rote shows that a variety of plane linkages can be convexified or straightened:</p> <p><a href="http://erikdemaine.org/papers/Linkage/" rel="nofollow">http://erikdemaine.org/papers/Linkage/</a></p> <p>Ileana Streinu recently won the Robbins Prize for very innovative approach to solving problems of this kind.</p> http://mathoverflow.net/questions/22767/is-the-area-of-a-polygonal-linkage-maximized-by-having-all-vertices-on-a-circle/22781#22781 Answer by Robin Chapman for Is the area of a polygonal linkage maximized by having all vertices on a circle? Robin Chapman 2010-04-27T21:06:29Z 2010-04-27T21:06:29Z <p>There's a simple argument showing that from the quadrilateral case we can easily deduce the $n$-vertex case (at least in the convex case). We claim that in any configuration locally maximizing the area the vertices are concyclic. Take any four consectutive vertices $A$, $B$, $C$ and $D$. Then in at a local maximum of area $A$, $B$, $C$ and $D$ are concyclic lest we could raise the area by moving the edges $AB$, $BC$ and $CD$ (by the quadrilateral case). Hence the circumcircles of $ABC$ and $BCD$ coincide. So all the circumcircles of three consecutive vertices are the same circle: the vertices are concyclic.</p> http://mathoverflow.net/questions/22767/is-the-area-of-a-polygonal-linkage-maximized-by-having-all-vertices-on-a-circle/22812#22812 Answer by Igor Pak for Is the area of a polygonal linkage maximized by having all vertices on a circle? Igor Pak 2010-04-28T06:24:30Z 2010-04-28T15:13:50Z <p>Here is a general way to think about these kind of problems. The Minkowski theorem says that a polytope is uniquely determined by its normals and volumes of the facets. You can loose some of these conditions and ask for the optimum isoperimetric ratio. In this case, in $\Bbb R^2$ you forget normals and conclude that inscribed polygon with given side lengths is optimal. A classical Lindelöf theorem does the opposite: in $\Bbb R^d$, it says that the optimal polytope with prescribed normals are circumscribed around the sphere (see e.g. <a href="http://www.springerlink.com/content/m388x8344gtx3731/" rel="nofollow">here</a>, Section 18.3).</p>