What is the smallest dilation of a quadrilateral in $\mathbb{R}^d$? This may be an open problem; 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].
            alt text

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

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 [as of July 2010, the original posting date]. 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!

  • 7
    $\begingroup$ A quadrilateral $P=ABCD$ in $\mathbb{R}^3$ may be viewed as two rigid triangles $ABC$ and $CDA$ hinged on the common edge $AC$ at a certain angle. After "unfolding" by increasing the angle to $\pi$, we get a flat quadrilateral, the Euclidean distance between any two points $x,y$ on the boundary $P$ weakly increases and the distance along the boundary stays the same, hence $\delta(x,y)$ weakly decreases. Conclusion: the smallest dilation is realized by a quadrilateral in $\mathbb{R}^2.$ $\endgroup$ – Victor Protsak Jul 10 '10 at 9:14
  • $\begingroup$ Convincing argument, Victor! $\endgroup$ – Joseph O'Rourke Jul 10 '10 at 12:15
  • $\begingroup$ This problem looks interesting, but I'm a little confused by the definitions. In the definition of $\delta(x, y)$, what are we taking the maximum over? In the definition of $\delta(P)$, did you mean maximum, not minimum? $\endgroup$ – Ravi Boppana Jul 12 '10 at 11:20
  • $\begingroup$ @Ravi: Sorry for the confusion. I meant this. Fixing $P$, you take the max over all pairs of points on $P$. That is the worst dilation of $P$. Then one wants the min over all $P$ (the way I phrased it, for a fixed number $n$ of vertices). So if you fix $P$ to be an equilateral triangle, then its dilation is 2 as per the figure. It turns out that every triangle has at least this dilation. So the min dilation for triangles is 2. What is unknown is the min dilation for quadrilaterals. It is only known to be at least 1.66. $\endgroup$ – Joseph O'Rourke Jul 16 '10 at 20:04

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.
          [alt text]

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$:
          alt text

  • 1
    $\begingroup$ @TonyK: Added a drawing of your first trapezium. $\endgroup$ – Joseph O'Rourke Jul 21 '10 at 1:06
  • $\begingroup$ @TonyK: Great work! Could you please specify the resulting quadrilateral in some definitive form? I am having some difficulty extracting exactly what is "the trapezium above." $\endgroup$ – Joseph O'Rourke Aug 12 '10 at 21:53
  • $\begingroup$ OK: in the diagram, replace 13 by 1; 5 by cos 2*theta; and 66/13 by w (where theta is 0.5555166235227462... radians, and w is to be determined). The perimeter P is 2*(cos 2*theta + w + 1), and the height h is sin 2*theta. Now just solve for w so that the discrepancy P/2h is equal to 1.89615765267304... $\endgroup$ – TonyK Aug 14 '10 at 20:01
  • $\begingroup$ I have realised that I can get an almost optimal (and rigorous) lower bound on the discrepancy, by combining my computer search with continuity results: under certain conditions, we can rely on the fact that if B and C each move less than a distance epsilon, then the discrepancy of the quadrilateral changes less than some linear function of epsilon. So we can rigorously delete finite regions from the search space, not just points. But the details are messy, and the end result is still just a numerical lower bound. So I probably won't see it through, unless one of you nags me about it. $\endgroup$ – TonyK Aug 14 '10 at 20:08
  • $\begingroup$ @Joseph: Your new diagram is correct. I just ran my program again, this time outputting points B and C; if A is (0,0) and D is (1,0), then B is (g,h) and C is (1-g,h), where g = 0.38822302188... and h = 0.78404544057... This agrees with your coordinates, after scaling. $\endgroup$ – TonyK Aug 16 '10 at 19:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.