Prove that the points can be covered by a heptagon of area $\dfrac{10}{3}$

Question

I am working on this problem:

There is a finite number of points in the plane, any three points form a triangle of area 1 or less. Prove that the points can be covered by a heptagon of area $\dfrac{10}{3}$.

In past, I solved a similar problem: "There is a finite number of points in the plane, any three points form a triangle of area 1 or less. Prove that the points can be covered by a triangle of area 4".

I think that the above statement is false, but I can find a counterexample. Anyone can help me solve this problem or find a counterexample?

Answer 1

You statement is true. In fact, you can always cover the points by an quadrilateral or hexagon with area at most $3$.

---

Given any $n$ points $v_1, v_2,\ldots, v_n \in \mathbb{R}^2$ such that all the triangles $\triangle_{v_iv_jv_k}$ have area at most $1$.

Let $P = \text{co}(v_1,v_2,\ldots,v_n)$ be their convex hull. Let $A, B, C \in \{ v_i \}$ be three vertices of $P$ so that $\verb/Area/(\triangle_{ABC})$ is largest. Since affine transform preserve convexity and ratio of area, we only need to study the case where $\triangle ABC$ is an equilateral triangle of area $1$.

Let $A'$ be the mirror image of $A$ with respect to segment $BC$. Define $B'$, $C'$ in a similar manner. $A', B', C'$ forms an equilateral triangle of area $4$. Since $P$ is convex and $\triangle ABC$ is the largest triangle inside $P$, we have $P \subset \triangle A'B'C'$.

If $P$ lies completely within one of the quadrilaterals $ABA'B'$, $BCB'C'$ or $CAC'A'$, then we can cover $P$ be an quadrilateral of area $3$. If not, pick point $D, E, F$ among the vertices of $P$ such that

• $D \subset \triangle AC'B$ with $d$, the distance between $D$ and segment $AB$ largest.
• $E \subset \triangle BA'C$ with $e$, the distance between $E$ and segment $BC$ largest.
• $F \subset \triangle CB'A$ with $f$, the distance between $F$ and segment $CA$ largest.

Following is a figure illustrating the geometry

$\hspace0.5in$

Consider the hexagon $ADBECF$, it is a convex polygon and its area is equal to $$\verb/Area/(ABCDEF) = 1 + \frac{d+e+f}{h}$$ where $h = \sqrt[4]{3}$ is the height of $\triangle ABC$.

It is clear $\triangle ABC$ is the largest triangle inside hexagon. There is a theorem which states that the ratio of the area of the largest triangle inside an convex hexagon is at least $\frac{4}{9}{}^{\color{blue}{[1]}}$. This leads to

$$1+\frac{d+e+f}{h} \le \frac{9}{4} \quad\implies\quad \frac{d+e+f}{3h} \le \frac{5}{12}$$

Construct

• a line through $D$ parallel to $AB$ and let it intersect $AC'$ at $A_c$, intersect $BC'$ at $B_c$.
• a line through $E$ parallel to $BC$ and let it intersect $BA'$ at $B_a$, intersect $CA'$ at $C_a$.
• a line through $F$ parallel to $CA$ and let it intersect $AB'$ at $A_b$, intersect $CB'$ at $C_b$.

It is easy to see $P$ lies in the hexagon $A_cB_cB_aC_aC_bA_b$ with area

$$\begin{align} \verb/Area/(A_cB_cB_aC_aC_bA_b) &= 4 - \left(1-\frac{d}{h}\right)^2 - \left(1-\frac{e}{h}\right)^2 - \left(1-\frac{f}{h}\right)^2\\ &\le 4 - 3\left(1 - \frac{d+e+f}{3h}\right)^2 \le 4 - 3\left(1 - \frac{5}{12}\right)^2 = \frac{143}{48} < 3 \end{align} $$

Combine these, we find it is always possible to cover $P$ and hence the points $v_1, \ldots, v_n$ by a quadrilateral or hexagon with area $\le 3$.

Your statement is a trivial consequence of this.

Notes/References

• $\color{blue}{[1]}$ - Fleischer, R., Mehlhorn, K., Rote, G., Welzl, E., & Yap, C.-K. (1992).
  Simultaneous Inner and Outer Approximation of Shapes.
  Algorithmica, 8, 365-389