A convex cover for closed unit curves has area at least 0.1

Moser’s worm problem is one of many unsolved problems in geometry posed by Leo Moser [11] in 1966 (see [12] for a new version). It asked about the smallest area of region $S$ in the plane which can be rotated and translated to cover every unit arc. While this problem is still open, lower and upper bounds for this smallest area are available in the literature. The current best upper bound $0.260437$ was established by Norwood and Poole [13]. For the lower bound, it is known only that the area of $S$ is strictly positive [10].

This problem can be modified by restricting region $S$ (e.g. triangle, rectangle, convex, non-convex, ect.) or restricting unit curves (e.g. closed, convex, ect.). Numerous problems in the worm family have been solved prior, see Wetzel [17] for a survey.

If we require $S$ to be convex, and cover arbitrary unit curves, the existence of the solution is shown by Laidecker and Poole [9] using Blachke Selection Theorem. In 2019, Panraksa and Wichiramala [14] showed that the Wetzel’s sector is a cover for unit arcs which has an area of $\pi/12\approx 0.2618$. This cover is the current upper bound for this problem, whereas the current lower bound $0.232239$ was found by Khandhawit, Sriswasdi and Pagonakis [8] in 2013.

The problem of finding smallest convex region $S$ to cover all (not necessarily unit) curves of diameter one was posed by Henri Lebesgue in 1914 and is known as Lebesgue’s universal covering problem. In this case, the current best lower and upper bounds are $0.832$ and $0.8440936$ due to Peter Brass and Mehrbod Sharifi [1] and Philip Gibbs [6], respectively.

In this paper, we consider the problem of covering closed unit curves by a convex region of the smallest area.

In 1957, H.G. Eggleton [3] showed that the equilateral triangle of side ${\displaystyle\frac{\sqrt{3}}{\pi}}$ is the smallest triangle which can cover all unit closed curves and its area is $\frac{3\sqrt{3}}{4\pi^{2}}\approx 0.13162$. Twenty five years later, the smallest rectangle with lengths $\frac{1}{\pi}$ and $\sqrt{\frac{1}{4}-\frac{1}{\pi^{2}}}$ is found by Shaer and Wetzel [15] and its area is about $0.12274$.

Furedi and Wetzel [5] decreased this area by clipping one corner of this rectangle with area about $0.11222$. Also, they modified this pentagon to a curvilinear hexagon which has an area of less than $0.11213$. In 2018, Wichiramala [18] showed that the opposite corner of the pentagon can be clipped to be a hexagonal cover with area less than $0.11023$ which is the best currently known bound.

Our work focuses on a lower bound for this problem. Chakerian and Klamkin [2] applied Fáry and Rédei’s theorem [4] to find the first lower bound which is $0.0963275$ by considering the convex hull of circle and line segment in 1973. Further, Furedi and Wetzel [5] showed that the minimum area of convex hull of circle and the $0.0261682\times 0.4738318$ rectangle has area $0.0966675$. Moreover, they replaced this rectangle by curvilinear rectangle and give a new lower bound about $0.096694$.

To improve this bound, one may consider the minimal convex hull of three given closed curves. However, in this case Fáry and Rédei’s theorem [4] can not be applied to find smallest area analytically, which complicates the analysis and call for the mix of geometric and numerical methods. Som-am [16] applied Brass grid method [1] to prove that the area of convex hull of circle, line segment ,and equilateral triangle is at least $0.096905$. In 2019, Grechuk and Som-am [7] used the Box search method to show that the minimal-area convex hull of the rectangle of perimeter $1$, circle with perimeter $1$, and the equilateral triangle with perimeter $1$, is greater than $0.0975$. Thus, if we denote $\alpha$ to be the area of smallest cover of closed unit curves, then

In this paper, we use geometric methods combined with the Box search algorithm to prove that the area of convex cover for the line segment, circle, and certain rectangle of perimeter $1$ is at least $0.1$.

By Theorem 1.1, we have

which improves the previous bound $0.0975$. In fact, the true minimal area of $S$ in Theorem 1.1 is about $0.10044$, but we have rounded the bound to $0.1$ to simplify the proof.

The choice of line segment, circle, and rectangle in Theorem 1 was not an arbitrary or lucky one. In fact, we have used a systematic search for three shapes which gives the best possible lower bound.

The organization of this paper is as follows. A systematic search for three shapes which maximal possible area of minimal convex hull is presented in Section 2. The remaining sections are devoted to the proof of Theorem 1.1. Section 3 proves some geometric lemmas. Section 4 describes numerical box-search algorithm and computational results. The proof of Theorem 1.1 is finished in Section 5. We give some conclusions in Section 6.

Theorem 1.1 establishes a new lower bound for the area of a convex cover for closed unit curves, by proving that a convex hull of three such curves, circle, line, and certain rectangle, must have area at least $0.1$. In fact, the choice of these three curves was not an arbitrary or lucky one, but was the result of a systematic numerical search, which we will describe in this section.

This section contains neither proofs nor any form of rigorous analysis, and the reader who is interested only in the proof of Theorem 1.1 can go straight to the next sections. However, this section is important to understand how we selected three curves considered in Theorem 1.1, and provides some guide were to not look when trying to substantially improve our lower bound.

For each specific set of unit curves, we write a program which finds minimum area of a convex hull of these curves, where the minimum is taken with respect to all translations and rotations of the curves. We then modify the curves to make this minimal as large as possible. This result is a maximin problem with highly non-smooth and non-convex objective function. We used Matlab function, patternsearch, with random initial data to try to find the global optimal value in various cases.

Let $\alpha$ be the area of smallest cover of closed unit curves. We will approximate curves by polygons, and it is clear that it suffices to consider convex polygons only. Let us start with 2 polygons. Let $F(X_{1},X_{2})$ be the area of convex hull of polygons $X_{1}$ and $X_{2}$. Let $\mathcal{T}$ be the set of all orientation-preserving motions $T$ of the plane (that is, all possible compositions of rotations and translations). Then, given any two polygons $X_{1}$ and $X_{2}$ with unit perimeter, the solution of the minimization problem

is the lower bound for $\alpha$.

Now, our aim to find polygons $X_{1}$ and $X_{2}$ for which this lower bound is as large as possible. Let $N_{1}$ and $N_{2}$ be a number of vertices in polygons $X_{1}$ and $X_{2}$ respectively. We assume that $N_{1}$ and $N_{2}$ are fixed but $X_{1}$ and $X_{2}$ can vary. Let $\mathcal{X}(N)$ be the set of all convex polygons with $N$ vertices and unit perimeter. We consider optimization problem

It is clear that for any $N_{1}$, $N_{2}$,

or, in words, $b(N_{1},N_{2})$ is a lower bound for $\alpha$.

Let $C$ be a circle of perimeter $1$, $R$ be a rectangle of size $u\times v$ where $u=0.1727$ and $v=\dfrac{1}{2}-u$, and $L$ be line of length $\dfrac{1}{2}$.

Let us fix the center of circle to be $C_{0}(0,0)$. Let $F$ be a regular $500$-gon inscribed in $C$, such that the sides of $R$ are parallel to some longest diagonals of $F$. Let $X$ be a union $F\cup R\cup L$. $X$ is called a configuration. Let $\mathcal{H}(X)$ be the convex hull of $X$, and $\mathcal{A}(X)$ be the area of $\mathcal{H}(X)$. Our aim is to find a configuration $X$ with the smallest $\mathcal{A}(X)$.

Let $R_{0}(x_{1},y_{1})$ be the center of $R$. By the symmetry of circle, we may assume that $x_{1},y_{1}\geq 0$. We have the vertices of $R$ are $R_{1}\left(x_{1}-v/2,y_{1}+u/2\right)$, $R_{2}\left(x_{1}+v/2,y_{1}+u/2\right)$, $R_{3}\left(x_{1}+v/2,y_{1}-u/2\right)$, and $R_{4}\left(x_{1}-v/2,y_{1}-u/2\right)$. Let $L_{0}(x_{2},y_{2})$ be the center of $L$ and $\theta$ be the angle between X axis and $L_{0}L_{2}$, see Figure 4.

The vertices of $L$ are $L_{1}(x_{2}+\frac{1}{4}\cos(\theta+\pi),y_{2}+\frac{1}{4}\sin(\theta+\pi))$ and $L_{2}(x_{2}+\frac{1}{4}\cos(\theta),y_{2}+\frac{1}{4}\sin(\theta))$. Note that any configuration $X$ is represented by $x_{1},y_{1},x_{2},y_{2}$, and $\theta$. Clearly, $0\leq\theta\leq\pi$

We define the function $f:\mathbb{R}^{5}\rightarrow\mathbb{R}$ by mapping vector $(x_{1},y_{1},x_{2},y_{2},\theta)$ to $\mathcal{A}(X)$. Clearly, $f$ is a continuous function. Since $F$ is a subset of $C$, it suffices to show that

This would immediately imply Theorem 1.1.

Next, we will apply result of Fary and Redei [4], and Lemma 1 and Corollary 2 in [7] to bound parameters $x_{1},y_{1},x_{2},y_{2}$ and $\theta$.

We prove Lipschitz continuity of $f$ in $Z$ in the following lemma

Let $Z$ be a region in Lemma 3.1. In this section, we prove that

by using box-search method as described in [7]. The method works as follows. Let $z^{*}$ be the center of a box $B$ which has the form $B=[a_{1},b_{1}]\times[a_{2},b_{2}]\times[a_{3},b_{3}]\times[a_{4},b_{4}]\times[a_{5},b_{5}]$. On every step, we check if

where $d_{i}$ is a half of the length of $[a_{i},b_{i}]$. If (4.1) holds, then inequality $f(z)>0.1$ holds for every $z\in B$ by Lemma 3.3.

If (4.1) does not hold, we will select the largest length, say $[a_{1},b_{1}]$ and split $B$ into two boxes $B_{1}=[a_{1},(a_{1}+b_{1})/2]\times[a_{2},b_{2}]\times[a_{3},b_{3}]\times[a_{4},b_{4}]\times[a_{5},b_{5}]$ and $B_{2}=[(a_{1}+b_{1})/2,b_{1}]\times[a_{2},b_{2}]\times[a_{3},b_{3}]\times[a_{4},b_{4}]\times[a_{5},b_{5}]$. Then, if (4.1) holds for both boxes $B_{1}$ and $B_{2}$, then $f(z)>0.1$ holds for every $z\in B_{1}$ and for every $z\in B_{2}$, hence it holds for every $z\in B$. If (4.1) does not hold for either $B_{1}$ or $B_{2}$ (or both), we subdivide the corresponding boxes again and proceed iteratively.

We start with $B=Z$, and, when the program halts, we are guaranteed that $f(z)>0.1,\forall z\in Z$.

Let us illustrate the first step of this procedure. By Lemma 3.1, we start with $B=Z=[0,0.0741]\times[0,0.0976]\times[-0.148,0.148]\times[-0.148,0.148]\times[0,\pi]$. Then we check (4.1) for $z^{*}=(0.03705,0.0488,0,0,\pi/2)$. In this case, (4.1) dose not hold because $f(z^{*})\approx 0.11851$ and $f(z^{*})-\sum\nolimits_{i=1}^{5}d_{i}C_{i}\approx-0.21937<0.1$. Thus, we must select the maximum length to subdivide $B$ into $B_{1}$ and $B_{2}$. In this case, $b_{5}-a_{5}=\pi\approx 3.14$ is the maximum. Hence, we divide $B$ into $B_{1}=[a_{1},b_{1}]\times[a_{1},b_{2}]\times[a_{3},b_{3}]\times[a_{4},b_{4}]\times[a_{5},(a_{5}+b_{5})/2]$ and $B_{2}=[a_{1},b_{1}]\times[a_{1},b_{2}]\times[a_{3},b_{3}]\times[a_{4},b_{4}]\times[(a_{5}+b_{5})/2,b_{5}]$. Then we check (4.1) for $B_{1}$ and for $B_{2}$ and repeat this procedure iteratively.

We run the Box-search algorithm [7] by using Matlab$\circledR$ R2018a, see implementation details and Matlab code in Appendix. The programme halts after $n=527,754,566$ iterations. This rigorously proves that the minimal area $\mathcal{A}(X)$ is greater than $0.1$. Numerically, the program returned value $0.10044$ for this minimal area, with optimal configuration $x_{1}=0.00434,\,y_{1}=0.00648,\,x_{2}=0.00434,\,y_{2}=-0.00434,\,\theta=0.85711$ see Figure 15.

In this work, we improve the lower bound for the area of convex covers for closed unit arcs from $0.0975$ to $0.1$. First, we used the geometric method to prove Lipschitz bounds for configuration function in $5$ parameters which represent the circle, $0.1727\times 0.3273$ rectangle, and line. Next, we used the numerical box-search algorithm developed in [7] to prove the main theorem. In fact, we have used regular $500$-gon in place of circle for convenience of Matlab numerical computations.

The best bound we can in principle get from circle-line-rectangle configuration is $0.10044$. To improve beyond this, different configurations of objects should be considered. The numerical results in Section 2 suggest that no configuration of three objects can give a bound much better than this. Because considering $4$ and more objects significantly increases the number of parameters and is computationally difficult, it looks like bound $0.1$ (or slightly better) may be the limit of the current technique, and substantially new ideas are required to significantly improve it.