# What is the area of the biggest open convex set inside the unit square not containing k points?

Given $k\in \mathbb N$, and $k$ points inside the unit square there should be an arrangement that minimizes the area of the biggest open convex set inside the unit square not containing these points. For example for $k=1$, by putting the point in the center you reduce this area to 1/2.

It is clear that this area is greater than or equal to $\frac{1}{k+1}$. Are there formulas or bounds for this area, for some small $k$´s?

I believe this is an open problem. This 2014 paper

Dumitrescu, Adrian, Sariel Har-Peled, and Csaba D. Tóth. "Minimum convex partitions and maximum empty polytopes." Scandinavian Workshop on Algorithm Theory. Springer Berlin Heidelberg, 2012. (2014 arXiv Abstract).

says it is

"a longstanding open problem by Danzer and Rogers [2, 6, 10, 19, 35]: What is the maximum volume of an empty convex body $C \subset [0, 1]^d$ that can be found amidst any set $S \subset [0, 1]^d$ of $n$ points in a unit cube? The current best bounds are $\Omega(1/n)$ and $O(\log n/ n)$, respectively (for a fixed $d$). The lower bound, for instance, can be deduced by decomposing the unit cube by $n$ parallel hyperplanes, each containing at least one point, into at most $n+ 1$ empty convex bodies. The upper bound is tight apart from constant factors for $n$ randomly and uniformly distributed points in the unit cube. It is suspected that the largest volume is $\omega(1/n)$ in any dimension $d \ge 2$."

• I know the open problem by Danzer and Rogers, but my questions is about some values for small $k$, for instance for k=2, the area is 1/2. But some results for k=3,......10, for example. – Gerardo Arizmendi May 19 '17 at 18:36

A warm up.

Let as define, as above, $\ a(X)\$ to be the supremum of the area of convex sets of $\mathbb I^n\setminus X$. Then let $\ a_n\$ be the minimum of $\ A(X)\$ over all $\ X\subseteq \mathbb I^n$ such that $\ |X|=n$.

It was stated in this thread that $\ a_n\ge\frac 1{n+1}\$ for every $n=1\ 2\ \ldots\ .\$ Actually:

$$a_n = \frac 12\qquad (n=1,2)$$ and $$a_n \ge \frac 1n\qquad (n\ge 2)$$

The proof of the later statement is simple: Let $\ |X|=n\ge 2\$ for an $\ X\subseteq\mathbb I^2.\$ Consider a straight line through any two different points of $\ X,\$ and parallel lines through the remaining points of $\ X.\$ There are at the most $\ n-1\$ of such parallel. At least one of the stripes between the neighboring two of them or one of the outside areas has are at least $\ \frac 1n,\$ i.e. $\ a_n\ge \frac 1n$.

Now, the first statement is pretty obvious (most of it has already been proved).

In the general case of $\ \mathbb I^d,\$ we have:

$$a^d(n)\ =\ \frac 12\qquad (n\le d)$$ and $$a^d(n)\ \ge\ \frac 1{n+2-d}\qquad (n\ge d)$$

REMARK:   The above results hold for the arbitrary convex set $\ J\subseteq \mathbb R^d\$ of d-measure $1$ (in place of $\ \mathbb I^d$).

Gerardo has asked about estimates for $a_k$, for small values of $k$, where for instance $\ a_4\$ is the maximal area of convex sets $\ X\subseteq \mathbb I^2\setminus Q\$ for the worst $4$-element subset $\ Q\subseteq\mathbb I^2,\$ i.e. for $\ Q\$ which leads to the minimal said maximum.

A casual estimate was $a_k\ge\frac 1{k+1}$, then a virtually equally simple estimate (see my first answer above) was $\ a_k\ge \frac 1k\$ for every $\ k\ge 2\$ in $\ \mathbb I^2,\$ e.g. $\ a_4\ge\frac 14.\$ This time I'll estimate $\ a_4\$ again, and this time I hope that my estimate is actually exact (in my second answer above there was also a specific estimate for $\ a_3$) :

Theorem $$a_4\ \ge \frac 13$$

Proof:

First consider consider a case where one of the points $\ a\in Q\$ belongs to the convex hull of $\ Q\setminus\{a\}.\$ Then the rays (half-lines) which start from point $\ a\$ and go through the remaining points of $\ Q\$ divide $\ \mathbb I^2\$ into three convex sets, the union of which (or of which closures) gives the entire square, and their interiors are disjoint with $\ Q).\$ Thus one of these interiors has area $\ge \frac 13$.

Now let's consider the remaining case where no point of $\ Q\$ belongs to the convex hull of the set of the remaining three points of $\ Q.\$ Then we may split $\ Q\$ into a union of two pairs $\ \{a\ b\}\$ and $\ \{c\ d\}\$ such that each pair belongs to the same side of the straight line which goes through the other pair. In other words, the are two half-planes $\ G\ H\$ such that each has one pair on its edge while being disjoint with the other pair. We have a decomposition of $\ \mathbb I^2\$ into a union of three convex sets $\,\ G\cap\mathbb I^2\,\$ and $\,\ H\cap\mathbb I^2\,\$ and $\ (\mathbb I^2\setminus G)\cap(\mathbb I^2\setminus H).\$

The interiors of these sets are disjoint from $\ Q,\$ and at least one of them has area $\ge\frac 13\,.$

End of proof

Conjecture $$a_4\ =\ \frac 13$$

More specifically, let $\ \mathbb I^2\ := [0,1]^2,\$ and $$\ Q :=\ \left\{ \left(\frac 13 , \frac 13\right) \ \ \left(\frac 13 , \frac 23\right) \ \ \left(\frac23 , \frac 13\right) \ \ \left(\frac 23 , \frac 23\right)\right\}$$

Then every convex set $\ A\subseteq \mathbb I^2\setminus Q\$ has area $\le \frac 13\$ (This conjecture reminds me the Minkowski's theory of convex sets).

• you forgot the , in points in $Q$. – Gerardo Arizmendi May 25 '17 at 15:53
• Although this is not a problem in your proof, you can fix the proof , why does the planes do not intersect? – Gerardo Arizmendi May 25 '17 at 16:22
• Just in case, the half-planes $\ G\ H\$ may intersect each other. When the area of their intersection is equal to $\ s>0\$ then one of the said three areas is at least $\ \frac 13+\frac s3 > \frac 13$. – Włodzimierz Holsztyński May 25 '17 at 19:22
• your totally right, nice proof! – Gerardo Arizmendi May 25 '17 at 20:06
• Oh, now I see it. It's about my style of formatting mathematics. Since $\ (a,b)\$ stands for an ordered pair most of the time, I use $\ (a;b)\$ for an interval (say, real interval), from $a$ to $b$. *** Also, since the Chinese and Gutenberg time, we can use space (blank character) to separate objects. To me symbols "," are an eyesore. Most of the time blank characters are so much nicer. Thus I write $\ (a\ b\ c)\$ or $\ \{a\ b\ c\}\$ for ordered and unordered lists (sets). Etc. – Włodzimierz Holsztyński May 25 '17 at 23:38

Let $\ a_3\$ be the maximal area of convex sets $\ X\subseteq \mathbb I^2\setminus T\$ for the worst $3$-element subset $\ T\subseteq\mathbb I^2,\$ i.e. for $\ T\$ which leads to the minimal said maximum. We saw in my earlier answer that $\ a_3\ge\frac 13.\$ My whole ambition here is to improve upon this bound (by  my ambition  I mean that I do not attempt to squeeze a still stronger result from my or any other method). The numerical result is stated at the very end of this text.

Thus, let $\ |T|=3.\$ If the center of the square $\mathbb I^2$ does not belong to the interior of the triangle $\ \triangle(T)\$ then the said maximal convex area outside $T$ is at least $\ \frac 12$.

From now on I assume that the center belongs to the interior of $\ \triangle(T)\$ (this means that $T$ is not collinear). The rest of the argument consists of two parts plus a conclusion.

Part 1.   Let $\ t\$ be the area of $\ \triangle(T).\$ Then the radius $\ r\$of the circle inscribed into the triangle satisfies inequality:

$$r\ \le\ 3^\frac {-3}4 \cdot t$$

Furthermore, the center of the square is between one of the straight lines of $\ T,\$ call it $L$, and the line parallel to $L$ which passes through the center of the inscribed circle. Let straight line $\ Ł \$ be parallel to $\ L,\$ and apart from the center of the square by $r$, and such that $L$ is between the center of the square and $Ł$.

We see that the (convex) side of the square outside of $\ Ł,\$ and away from from the said centers has area $\ \le\ \alpha := \frac 12 - r,\$

(EDIT I've just fixed the direction of this above inequality for area)

i.e.

$$\alpha\,\ \ge\,\ \frac 12\ -\ 3^\frac {-3}4 \cdot t$$

This way we have obtained a convex set of area $\alpha$ which is disjoint with the interior of $\triangle(T)$.

Part 2:   The three straight lines which pass through the pairs of points of $T$ form some kind of a Venn diagram (not really) which consists of $\triangle T$, of three angular areas $\ K_1\ K_2\ K_3,\$ and of three infinite triangles (to me they look like infinite trapezoids, but never mind) $\ B_1\ B_2\ B_3.\$ The enumeration is such that $\ K_i\cap B_i=\emptyset\$ for each $\ i=1\ 2\ 3$.

Every union

$$S_{ijm}\ :=\ K_i\cup B_j\cup K_m$$

combines to one side of the said straight lines, which is disjoint with the interior of $\ \triangle(T),\$ whenever $\ i+j+m = 6\$ and $\ |\{i\ \ j\,\ m\}| = 3.\$

Let $\ \sigma\$ be the sum of the areas of $S_{123}$ and $S_{231}$ and $S_{312}.\$ Let $\ \kappa\$ be the area of $\ K_1\cup K_2\cup K_3.\$ Let $\ \gamma\$ be the sum of areas of $\ \triangle(T)\cup B_1\$ and $\ \triangle(T)\cup B_2\$ and $\ \triangle(T)\cup B_3.\$ Then:

$$2\cdot\sigma + \gamma\ =\ 3 + 2\cdot t + \kappa$$ hence $$2\cdot\sigma + \gamma\ \ge\ 3 + 2\cdot t$$

The left-hand side expression is the sum of $9$ convex sets which have pair-wise disjoint interiors, and which have their interiors disjoint from $T$--these convex sets are of the form $S_{ijm}$ and $K_i\cup\triangle(T)$. Thus, at least one of these $9$ sets has area

$$\beta\ \ge \frac 13 + \frac 29\cdot t$$

Conclusion   The above estimates for $\alpha$ and $\beta$ are a decreasing and increasing function respectively. They are equal at

$$t_0\ :=\ \frac 16\cdot\left(\frac 29 + 3^\frac{-3}4\right)^{-1}$$

By considering the case $\ t\le t_0$, then $\ t\ge t_0\$ respectively, we obtain:

Theorem $$a_3\,\ \ge\,\ \frac 12\ -\ 3^\frac{-3}4 \cdot t_0\,\ = \,\ \frac 13\ +\ \frac 29\cdot t_0$$

In case you are curious about the numerical value of the just obtained lower bound on $a_3$, it is: $$a_3\ \ge\ 0.38937\ldots$$ (I am glad that it is clearly greater than $\ \frac 13$).

@JosephO'Rourke has passed to us the following:

The current best bounds are $\Omega(1/n)$ and $O(\log n/ n)$, respectively (for a fixed $d$). The lower bound, for instance, can be deduced by decomposing the unit cube by $n$ parallel hyperplanes, each containing at least one point, into at most $n+1$ empty convex bodies.

(This means a lower bound of $a^\nu_n \ge \frac 1{n+1}$, where $\nu$ is the dimension of space $\mathbb R^\nu$). Let me provide a simple lower bound (sharper than $\frac 1{n+1}$), together with a simple proof.

Instead of a single convex set like $\mathbb I^\nu$, let's consider the inf over all convex sets of measure $1$. Then the new lower bounds $b^\nu_n$ will be smaller, will satisfy $b^\nu_n\le a^\nu_n$ (but they will be still clearly better than $\frac 1{n+1}$).

Consider $\ \mathbb R^\nu.\$ Define $\ b^\nu(A)\$ as the sup of $\ \frac {\mu(C)}{\mu(A)}\$ taken over all convex sets $\ C\subseteq A,\$ for arbitrary measurable set $\ A\subseteq\mathbb R^\nu$ of finite positive measure (not necessarily $1$).

The extension over arbitrary measures is just a convenience, it doesn't change anything.

Then $\ b^\nu_n\$ is defined as the inf over all said subsets $\ A\$ such that the convex hull of $A$ is obtained by adding exactly $n$ points, for $\ n=0\ 1\ 2\ \ldots$.

Note:   $\ 1=b^\nu_0\ge b^\nu_1\ge b^\nu_2\ge \ldots$

Let's start with a recursion (this will be $90\%$ of the argument):

Theorem 1   $\ \forall_{n\ge \nu}\quad b^\nu_n\ \ge \ \frac {b^\nu_{n-\nu}}{1\ +\ b^\nu_{n-\nu}}$

Proof Let $\ A\subseteq\mathbb R^n\$ have measure $1$, and be such that $\ A\cup N\$ is the convex hull of $\ A\$ for an $n$-element set $\ N,\$ where $\ A\cap N=\emptyset\$ (set $N$ is unique). Then there exists an affine $(n-1)$-plane $\ L,\$ which contains at least $\ \nu\$ differently points of $\ L,\$ and such that the remaining points of $N$ are on one side of $L$.

If the side which has no points of $N$ in its interior has measure at least $\ \frac {b^\nu_{n-\nu}}{1\ +\ b^\nu_{n-\nu}}$ then we are done. Otherwise, the other side has measure $\ \ge\ \frac 1{1\ +\ b^\nu_{n-\nu}}$. This side has at the most $\ n-\nu\$ points of $N$ in its interior. Thus this side minus $N$ contains a convex set of measure at least

$$\frac 1{1\ +\ b^\nu_{n-\nu}}\cdot b^\nu_{n-\nu}\ = \ \frac {b^\nu_{n-\nu}}{1\ +\ b^\nu_{n-\nu}}$$

That's all. End of PROOF

The rest doesn't require further comments:

Theorem 2   $\ \forall_{n\ge \nu}\forall_{m=0\ 1\ \ldots}\quad b^\nu_{n+m}\ \ge \ \frac {b^\nu_{n-\nu}}{1\ +\ (m+1)\cdot b^\nu_{n-\nu}}$

Theorem 3   $\ b^\nu_0=1\$ and $\ \forall_{n=1}^\nu\ \ b^\nu_n\ =\ \frac 12$

Theorem 4   $\ \forall_{t=0\ 1\ \ldots}\quad b^\nu_{t\cdot\nu}\ \ge\ \frac 1{t+1}$

Theorem 5   $\ \forall_{t=0\ 1\ \ldots}\forall_{q=1}^{\nu-1}\quad b^\nu_{t\cdot\nu+q}\ \ge\ \frac 1{t+2}$

Remark   In the special case of $\nu=2$ and $q=1$ we get a sharper bound from my earlier answer than we see it here in Theorem 5 (the restriction to $\ \mathbb I^2\$ from my previous answer was not essential).

EXAMPLE   Consider an arbitrary (non-degenerated) triangle $T\subseteq\mathbb R^2.\$ Then

$$\forall_{p\in T}\quad b^2_1(T\setminus\{p\})\ \ge\ \frac 59$$

Furthermore, for the center of gravity of $T$ we obtain:

$$b^2_1(T\setminus\{c\})\ =\ \frac 59$$

In a similar situation for the centrally symmetric convex sets $C$ and their center $c$, we get only $\frac 12$:

$$\forall_{p\in C}\qquad b^2_1(C\setminus\{p\})\,\ \ge\,\ \frac 12 \,\ \ge\,\ b^2_1(C\setminus\{c\})$$

• Wlod AA = Włodzimierz Holsztyński – Wlod AA May 29 '17 at 7:55