Can You Squeeze Your Quads?

Squeeze two quadrilaterals into a unit circle (a circle of radius $1$). They may share edges, parts of edges or corners, and their corners may sit on the circle itself, but their interiors may not overlap. Each may be convex or concave, but not “crossed” like a bowtie. What is the greatest combined area the two quadrilaterals can have?

The Fiddler, Zach Wissner-Gross, November 10, 2023(original post)

The official solution appeared in the post of November 17, 2023 and gives $3\sqrt3/2 \approx 2.598$ for the main puzzle and about $3.1488$ for the Extra Credit. Both agree with the answers below.

Solution

Start with a good arrangement. Cut a regular hexagon inscribed in the circle along one of its long diagonals. The two halves are congruent trapezoids, each a genuine quadrilateral, and together they fill the hexagon. The hexagon is six equilateral triangles of side $1$, each of area $\sqrt3/4$, so the pair covers $$6 \cdot \frac{\sqrt3}{4} \;=\; \frac{3\sqrt3}{2} \;\approx\; 2.598 ,$$ about $83$ percent of the circle.

The real work is to show that nothing does better. Two facts about polygons in a circle carry the argument.

Fact 1: the largest polygon with a given number of corners. Take a convex polygon with $m$ corners inside the unit disk. If one of its corners is strictly inside the disk, push that corner a little further from the line through its two neighbours. The polygon stays in the disk and gains area. So a largest such polygon has all its corners on the circle. Now join the centre to each corner. Neighbouring corners whose radii make an angle $g$ cut off a triangle of area $\tfrac12 \sin g$, so the polygon has area $$\tfrac12 \left( \sin g_1 + \sin g_2 + \dots + \sin g_m \right), \qquad g_1 + \dots + g_m = 2\pi .$$ (If one angle exceeds $\pi$, the centre lies outside the polygon and that triangle counts negatively, which the negative sine does automatically.) When every angle is below $\pi$, the sine curve bends downwards on that range, so the sum of sines with a fixed total is largest when the angles are equal: the regular polygon, with area $\tfrac m2 \sin(2\pi/m)$. When one angle reaches $\pi$, its sine is at most $0$ and the others total at most $\pi$, so the area is at most half their total, $\pi/2$, which is less anyway. The values $\tfrac m2 \sin(2\pi/m)$ grow with $m$, so any convex polygon with at most six corners has area at most that of the regular hexagon, $3\sqrt3/2$.

Fact 2: the largest quadrilateral in a slice of the disk. A straight line cuts the disk into two slices. Measure each slice by the angle $\beta$ its arc makes at the centre, so the two slices have $\beta$ and $2\pi - \beta$. Take a largest quadrilateral inside a slice. Pushing corners outwards as before, every corner ends on the boundary of the slice. A corner on the straight edge can slide along that edge to one of its ends without losing area (the area changes at a steady rate as the corner slides, so one direction or the other does not lose). So all four corners can be taken on the arc. If they cut it at angles $g_1, g_2, g_3$ with total $s \le \beta$, the closing angle is $2\pi - s$ and the area is $$\tfrac12\left(\sin g_1 + \sin g_2 + \sin g_3 - \sin s\right) \;\le\; \tfrac12\left(3 \sin\tfrac s3 - \sin s\right),$$ with equal angles again best. The right side increases with $s$ up to $s = 3\pi/2$ (its rate of change is $\tfrac12(\cos\tfrac s3 - \cos s)$, which is not negative there). So for $\beta \le 3\pi/2$, every quadrilateral in the slice has area at most $$f(\beta) \;=\; \tfrac12\left(3 \sin\tfrac\beta3 - \sin\beta\right),$$ and for larger $\beta$ at most $f(3\pi/2) = 2$, the inscribed square.

Fact 2 gives a clean bound for two quadrilaterals on opposite sides of a line. If both slices have $\beta$ and $2\pi - \beta$ at most $3\pi/2$, the two $\sin\beta$ terms cancel, since $\sin(2\pi - \beta) = -\sin\beta$, and $$\begin{align*} f(\beta) + f(2\pi - \beta) &= \tfrac32\left(\sin\tfrac\beta3 + \sin\tfrac{2\pi - \beta}{3}\right) \\ &= 3 \sin\tfrac\pi3 \cos\tfrac{\beta - \pi}{3} \;\le\; \frac{3\sqrt3}{2}, \end{align*}$$ with equality only when the line is a diameter. If one slice is larger than $3\pi/2$, the other is smaller than $\pi/2$, and the total is at most $2 + f(\pi/2) = 2.25$. Either way, two quadrilaterals separated by a line cover at most $3\sqrt3/2$. Equality needs two half-hexagons on a diameter, which is the arrangement we started with.

Putting it together. Let $H$ be the smallest convex region containing both quadrilaterals (stretch a rubber band around them). It is a convex polygon whose corners are some of the eight corners of the quadrilaterals, and it contains both, so the combined area is at most the area of $H$.

If $H$ has at most six corners, Fact 1 caps its area at $3\sqrt3/2$.

Otherwise $H$ has seven or eight corners, so at most one of the eight corners lies inside $H$. A concave quadrilateral has its inward-pointing corner inside the triangle formed by its other three, and so inside $H$. Hence at most one quadrilateral is concave.

• If both are convex, they can be separated by a straight line: two convex shapes whose interiors do not meet always can.

• If one, say $Q_1$, is concave, write $a, b, c$ for its corners on $H$ and $r$ for the inward one, so $Q_1$ is the triangle $abc$ with the notch $arc$ removed, and $ab$, $bc$ are edges of $Q_1$. The four corners of $Q_2$ are all corners of $H$, so none lies inside the triangle $abc$. If $Q_2$ reached into that triangle, one of its edges would have to cross the triangle, entering through one side and leaving through another. A straight edge meets the side $ac$ at most once, so it would cross $ab$ or $bc$, and next to those sides lies the interior of $Q_1$. That is not allowed. So $Q_2$ stays outside the triangle $abc$, and a straight line separates $Q_2$ from the triangle, which contains $Q_1$.

In both cases a line separates the two shapes, and the triangle in the second case is a quadrilateral with a corner to spare, so the bound for separated quadrilaterals applies. Every arrangement therefore covers at most $3\sqrt3/2$, and the two trapezoids reach it: $$\boxed{\ \text{greatest combined area} \;=\; \frac{3\sqrt3}{2} \;\approx\; 2.598. \ }$$

The computation

The program searches for good pairs directly. It describes the eight corners in polar form, clamps each radius to the disk, and scores a pair as its combined area, or as $-1$ if either quadrilateral crosses itself or the two interiors overlap. From random starts it moves one corner at a time by a shrinking random step and keeps any move that does not lower the score.

import math, random
from shapely.geometry import Polygon

def point(r, a):
    r = max(0.0, min(r, 1.0))       # stay inside the disk
    return (r * math.cos(a), r * math.sin(a))

def score(v):
    p = [point(*v[k]) for k in range(8)]
    A, B = Polygon(p[:4]), Polygon(p[4:])
    if not (A.is_valid and B.is_valid):
        return -1                    # a crossed (bowtie) shape
    if A.intersection(B).area > 1e-12:
        return -1                    # interiors overlap
    return A.area + B.area

random.seed(1)
best = 0
for start in range(8):
    v = [[1.0, random.uniform(0, 2 * math.pi)]
         for _ in range(8)]
    s = score(v)
    for it in range(20000):
        step = max(0.3 * 0.9993 ** it, 1e-5)
        k = random.randrange(8)
        w = [q[:] for q in v]
        w[k][0] += random.gauss(0, step)
        w[k][1] += random.gauss(0, step)
        t = score(w)
        if t >= s:
            v, s = w, t
    best = max(best, s)
print(f"best combined area found: {best:.3f}")

It prints

best combined area found: 2.598

which is $3\sqrt3/2$ to three decimal places. A search like this can only approach the best value from below, and it gets no further than the hexagon.

Extra Credit

For four distinct points on the unit circle, let $Z$ be the area of the quadrilateral they form plus the area of the largest triangle formed by any three of them. For the corners of a square, $Z = 2 + 1 = 3$. What is the greatest possible value of $Z$?

Solution

Label the points in order around the circle. Any three of them leave one out, so every triangle consists of one diagonal of the quadrilateral and one of the two corners off that diagonal. Call the largest triangle $ABD$, with diagonal $BD$, and let $C$ be the fourth point.

Two moves can only increase $Z$. Slide $A$ along its arc to the midpoint of that arc. This takes it as far from $BD$ as possible, which enlarges the triangle $ABD$ and with it the quadrilateral, since the quadrilateral is $ABD$ plus $CBD$. Then slide $C$ to the midpoint of its arc, which enlarges $CBD$ and so the quadrilateral again. The largest triangle is still at least $ABD$, so $Z$ has not dropped. After both moves $A$ and $C$ sit on the perpendicular bisector of $BD$, which passes through the centre, so $AC$ is a diameter and the shape is a kite.

Now one number describes everything. Let $x \ge 0$ be the distance from the centre to the chord $BD$, with $A$ on the far side. The chord has half-length $\sqrt{1 - x^2}$. Triangle $ABD$ has height $1 + x$ and $CBD$ has height $1 - x$, so $$\text{area } ABD = (1 + x)\sqrt{1 - x^2}, \qquad \text{kite} = 2\sqrt{1 - x^2},$$ and $ABD$ is indeed the largest triangle. Therefore $$Z(x) \;=\; (3 + x)\sqrt{1 - x^2}.$$ Setting the rate of change to zero and multiplying through by $\sqrt{1 - x^2}$, $$(1 - x^2) - x(3 + x) = 0 \quad\Longleftrightarrow\quad 2x^2 + 3x - 1 = 0 ,$$ whose root between $0$ and $1$ is $$x = \frac{\sqrt{17} - 3}{4} \approx 0.281 .$$ At $x = 0$ (the square) $Z = 3$ and at $x = 1$ it is $0$, so this turning point is the maximum. Substituting and simplifying gives $Z^2 = (107 + 51\sqrt{17})/32$: $$\boxed{\ Z_{\max} \;=\; \sqrt{\frac{107 + 51\sqrt{17}}{32}} \;\approx\; 3.1488. \ }$$ Amusingly, that is within $0.01$ of $\pi$.

The computation

The program works from the definition of $Z$: it places four points on the circle, computes the area of the quadrilateral they form (taking the points in order round the circle) and the largest of the four triangles, and climbs from random starts as before.

from itertools import combinations

def area(ps):
    n = len(ps)
    return abs(sum(ps[i][0] * ps[(i + 1) % n][1]
                   - ps[(i + 1) % n][0] * ps[i][1]
                   for i in range(n))) / 2

def Z(angles):
    ps = [(math.cos(a), math.sin(a))
          for a in sorted(a % (2 * math.pi) for a in angles)]
    return area(ps) + max(area(t) for t in combinations(ps, 3))

random.seed(1)
best = 0
for start in range(20):
    v = [random.uniform(0, 2 * math.pi) for _ in range(4)]
    s = Z(v)
    for it in range(5000):
        w = [a + random.gauss(0, 0.2 * 0.998 ** it) for a in v]
        if Z(w) >= s:
            v, s = w, Z(w)
    best = max(best, s)
print(f"greatest Z found: {best:.4f}")

It prints

greatest Z found: 3.1488