Smallest dilation of a quadrilateral? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T23:20:00Z http://mathoverflow.net/feeds/question/31262 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/31262/smallest-dilation-of-a-quadrilateral Smallest dilation of a quadrilateral? Joseph O'Rourke 2010-07-10T02:02:51Z 2010-08-16T13:41:25Z <p>What is the smallest dilation of a quadrilateral in $\mathbb{R}^d$? This may be an open problem, which I know is <em>verboten</em> on MO. So my question is: Is this indeed open?</p> <p>It will take me some time to explain the terms. The notion of <em>dilation</em> derives from Gromov, as far as I know (He defines a version in <em><a href="http://www.springer.com/birkhauser/mathematics/book/978-0-8176-4582-3" rel="nofollow">Metric Structures for Riemannian and Non-Riemannian Spaces</a></em>, p.11, although he called it <em>distortion</em>). I came upon it myself via <em>$t$-spanners</em>.</p> <p>The version in which I am interested is this. Let $P$ be a polygon (its boundary, not its interior), and $x,y$ two points on $P$. You can think of $P$ in $\mathbb{R}^2$, but also $\mathbb{R}^3$ and $\mathbb{R}^d$ for $d>3$ are interesting. Define $\delta(x,y)$ as the maximum (supremum) of $d_P(x,y) / | x y |$, where $d_P(x,y)$ is the distance between $x$ and $y$ following $P$ (the shortest path staying on the closed path that consitutes $P$), and $|xy|$ is the Euclidean distance in $\mathbb{R}^d$. Thus $\delta(x,y)$ measures how much $P$ <em>dilates</em> w.r.t. Euclidean distance. I am interested in the minimum value $\delta(P)$ of $\delta(x,y)$ over all $x,y \in P$, for all $n$-gons $P$, for fixed $n$.</p> <p><hr /> <b>Example 1.</b> If $P$ is a unit square, then $\delta(x,y)$ for $x,y$ opposite corners is $\sqrt{2}$, but $\delta(P)=2$ because with $x,y$ midpoints of opposite sides, $\delta(x,y)= 2/1$.</p> <p><b>Example 2.</b> If $P$ is an equilateral triangle, $\delta(P)=2$, as shown in the figure. In fact, the dilation of any triangle is $\ge 2$ [Lemma 7 in the 2nd paper below]. <br /><img src="http://cs.smith.edu/~orourke/MathOverflow/EqTriDilation.jpg" alt="alt text"></p> <p><b>Example 3.</b> It is known the the dilation of any closed curve $C$ satisfies $\delta(C) \ge \pi/2$, with equality achieved only by the circle. [Corollary 23 in the first paper below.] This is (apparently) due to Gromov.</p> <hr /> <p>So I finally come to my question. By reading these two papers, "<a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.61.7469" rel="nofollow">Geometric Dilation of Closed Planar Curves: New Lower Bounds</a>," and "<a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.61.6739" rel="nofollow">On Geometric Dilation and Halving Chords</a>," it appears to me that the minimum dilation of a quadrilateral in $\mathbb{R}^2$ (and $\mathbb{R}^d$) is not known. I had heard this was the case three years ago in a seminar in Brussels, but (a) I didn't quite believe it, (b) it was hearsay, and (c) it is now out of date. I am trying to clarify with the authors of these papers, but in parallel I would appreciate any information on the status of this question. The latter paper cited above proves a lower bound of $4 \tan(\pi/8) \approx 1.66$ (if I have interpreted it correctly).</p> <p>Finally, if indeed open, this seems a potential <a href="http://mathoverflow.net/questions/31153/problem-suggestions-for-polymath-for-undergraduates-research" rel="nofollow">PolyMath undergrad project</a>, as well as fun for anyone else!</p> <p><b>Addendum.</b> I don't want to close-out this question, but I have heard from one of the authors of the above cited papers, and indeed it appears that the dilation of a planar quadrilateral is unknown. So I have tentatively tagged this as an <em>open-problem</em>, and I will update if new information surfaces. Thanks for everyone's interest and input!</p> http://mathoverflow.net/questions/31262/smallest-dilation-of-a-quadrilateral/32723#32723 Answer by TonyK for Smallest dilation of a quadrilateral? TonyK 2010-07-21T00:41:07Z 2010-08-16T13:41:25Z <p><strong>Updated on 25th July -- see below</strong><br> Make an isosceles trapezium by starting with a rectangle of height 12 and width 66/13, and attaching Pythagorean (5,12,13) triangles to each side. Then the perimeter P is 600/13, and the height h is 12; and the numbers have been selected so that the width w at the equator is 12 too (where the equator is the horizontal line that divides the perimeter into two halves of equal length). So the dilation is P/2h = 25/13, which is less than 2. <br /> <img src="http://cs.smith.edu/~orourke/MathOverflow/Trapezium.jpg" alt="alt text"> <br /> </p> <p>We can try this with a general right-angled triangle. It is convenient to let the angle at the base of the trapezium be 2&theta;, so in our example we have sin 2&theta; = 12/13. We find that the dilation is equal to 1 + sin 2&theta;. However, if &theta; is too small, then we can achieve a larger dilation simply by cutting across the corner; this dilation is 1/sin &theta;. So we get the smallest dilation for an isosceles trapezium when 1/sin &theta; = 1 + sin 2&theta;. I had to resort to numerical methods to solve this; I got &theta; = 0.5555166235227462... radians, for a dilation of 1.89615765267304...</p> <p>We can't improve on this by using a non-isosceles trapezium, but a smaller dilation might be achieved by a general non-trapezoidal quadrilateral.</p> <p>Sorry if this all looks a bit provisional. If I get a full answer, I will put more effort into drawing some nice pictures and stuff.</p> <p><strong>Update</strong> I have carried out a computer search for the smallest dilation, as follows. Without loss of generality, we can restrict the search to quadrilaterals ABCD such that:<br> - A=(0,0), D=(1,0);<br> - B and C lie above the x-axis;<br> - all side lengths are &lt;= 1. </p> <p><em>Step 1:</em> Evaluate the dilation of all such quadrilaterals with x- and y-coordinates a multiple of 0.01. Save the 10000 quadrilaterals with the smallest dilation to file.<br> <em>Step 2:</em> For each B,C in the file, evaluate the dilation for the 10000 quadrilaterals with coordinates differing from B,C by a multiple of 0.001 between -0.005 and +0.004. (In other words, decrease the grid size by a factor of 10.) Of the resulting 100000000 quadrilaterals, save the 10000 with the smallest dilation to file.<br> <em>Step 3:</em> Repeat Step 2 with the grid size decreased by a factor of 10. And so on.</p> <p>This procedure converges on the isosceles trapezium described above. So while this is not a proof, it is likely that the smallest possible dilation of a quadrilaterlal is indeed 1.89615765267304... (which is the real root of the polynomial $x^5 - x^4 - 4x - 4$).</p> <p><b>Edit by J.O'Rourke</b> (16Aug10). If I've followed Tony's description in the comment below correctly, here is his quadrilateral with the (conjectured) smallest dilation: $h=0.896158$, $w=0.25552$: <br /> <img src="http://cs.smith.edu/~orourke/MathOverflow/QuadTony.jpg" alt="alt text"></p>