Smallest dilation of a quadrilateral?

2010-07-10T02:02:51Z

What is the smallest dilation of a quadrilateral in $\mathbb{R}^d$? This may be an open problem, which I know is verboten on MO. So my question is: Is this indeed open?

It will take me some time to explain the terms. The notion of dilation derives from Gromov, as far as I know (He defines a version in Metric Structures for Riemannian and Non-Riemannian Spaces, p.11, although he called it distortion). I came upon it myself via $t$-spanners.

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$ dilates 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$.

Example 1. 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$.

Example 2. 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].

Example 3. 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.

So I finally come to my question. By reading these two papers, "Geometric Dilation of Closed Planar Curves: New Lower Bounds," and "On Geometric Dilation and Halving Chords," 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).

Finally, if indeed open, this seems a potential PolyMath undergrad project, as well as fun for anyone else!

Addendum. 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 open-problem, and I will update if new information surfaces. Thanks for everyone's interest and input!

Answer by TonyK for Smallest dilation of a quadrilateral?

2010-07-21T00:41:07Z

Updated on 25th July -- see below
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.

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θ, so in our example we have sin 2θ = 12/13. We find that the dilation is equal to 1 + sin 2θ. However, if θ is too small, then we can achieve a larger dilation simply by cutting across the corner; this dilation is 1/sin θ. So we get the smallest dilation for an isosceles trapezium when 1/sin θ = 1 + sin 2θ. I had to resort to numerical methods to solve this; I got θ = 0.5555166235227462... radians, for a dilation of 1.89615765267304...

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.

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.

Update 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:
- A=(0,0), D=(1,0);
- B and C lie above the x-axis;
- all side lengths are <= 1.

Step 1: 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.
Step 2: 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.
Step 3: Repeat Step 2 with the grid size decreased by a factor of 10. And so on.

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$).

Edit by J.O'Rourke (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$:

Smallest dilation of a quadrilateral? - MathOverflow

Smallest dilation of a quadrilateral?

Answer by TonyK for Smallest dilation of a quadrilateral?