Convex polygons and separation of convex sets^††thanks: Partially supported by Conacyt, México.

A side $s$ of a polygon $P_{i}\in\mathcal{P}$ is reducible with respect to $\mathcal{P}$ if the triangle $t_{s}$ (not containing $P_{i}$), bounded by $s$ and the lines supporting the sides of $P_{i}$ incident to $s$, does not intersect the interior of any another polygon $P_{j}$. Equivalently, a side $s$ of a polygon $P_{i}\in\mathcal{P}$ is reducible with respect to $\mathcal{P}$ if it vanishes before reaching the interior of a polygon $P_{j}$ when it is translated in the direction orthogonal to $s$ and away from $P_{i}$ (see Fig. 1).

We modify $\mathcal{P}$ by growing, one at a time, polygons in $\mathcal{P}$ as follows: if some polygon $P_{i}\in\mathcal{P}$ has a reducible side $s$ with respect to $\mathcal{P}$ substitute $P_{i}$ in $\mathcal{P}$ with polygon $P_{i}\cup t_{s}$. Repeat this until no polygon in $\mathcal{P}$ has a reducible side. Denote by $\mathcal{R}=\{R_{1},R_{2},\ldots,R_{n}\}$ the family of polygons thus obtained.

Its is clear that $\mathcal{R}$ satisfies conditions 1) and 2), we claim it also satisfies condition 3. To prove this consider a third family $\mathcal{Q}=\{Q_{1},Q_{2},\ldots,Q_{n}\}$ of convex polygons obtained from $\mathcal{R}$ by further growing polygons $R_{1},R_{2},\ldots,R_{n}$ in the following way.

A side $s$ of a polygon $R_{i}$ in $\mathcal{R}$ is free with respect to $\mathcal{R}$ if the open polygonal region, not containing $R_{i}$, which is determined by $s$ and the lines supporting the two sides of $R_{i}$ adjacent to $s$ contains no points of polygons in $\mathcal{R}$.

Let $C$ be a circle containing all polygons in $\mathcal{R}$. Starting with the non free sides of polygons $R_{i}\in\mathcal{R}$, translate one at a time a side $s$ of a polygon $R_{i}\in\mathcal{R}$ (also in the direction orthogonal to $s$ and away from $R_{i}$) as far as possible without intersecting the interior of another (possibly already grown) polygon $R_{j}$ or the exterior of $C$ (see Fig. 2).

Stop when no side can be translated as indicated and let $\mathcal{Q}=\{Q_{1},Q_{2},\ldots,\allowbreak Q_{n}\}$ where, for $i=1,2,\ldots,n$, $Q_{i}$ is the polygon obtained from $R_{i}$ in this manner. We claim that if $C$ is chosen large enough, then each polygon in $\mathcal{Q}$ contains at most 3 free sides and all non free sides of a polygon $Q_{i}$ in $\mathcal{Q}$ are in contact with a polygon $Q_{j}$ with $i\neq j$.

By the choice of $\mathcal{R}$ no side of a polygon $R_{j}$ vanishes, therefore for $i=1,2,\ldots,n$ the number of sides of $R_{i}$ is equal to the number of sides of $Q_{i}$.

We define a plane graph $G$ with one vertex $v_{i}$ placed in the interior of each polygon $Q_{i}\in\mathcal{Q}$ and a vertex $v_{n+1}$ placed outside circle $C$. The edge set of $G$ consists of 6 types of edges as follows:

a) If a side of a polygon $Q_{i}$ and a side of a polygon $Q_{j}$ have a segment $l$ in common choose an arbitrary point $p$ in $l$ and draw an edge $v_{i}v_{j}$ through $p$ as in Fig. 3 (left).

b) If a vertex $p$ of a polygon $Q_{i}$ lies in the interior of a side of a polygon $Q_{j}$ and $p$ is not a vertex of a polygon in $\mathcal{Q}$ other than $Q_{i}$, then draw an edge $v_{i}v_{j}$ through $p$ as in Fig. 3 (center).

c) If two or more polygons $Q_{i_{1}},Q_{i_{2}},\ldots,Q_{i_{r}}$ share a vertex $p$ which lies in the interior of a side of a polygon $Q_{j}$ and $p$ is not a point of any polygon $Q_{k}$ other than $Q_{i_{1}},Q_{i_{2}},\ldots,Q_{i_{r}}$, then there is a neighbourhood $N$ of $p$ containing no points of polygons $Q_{k}$ with $k\neq j,i_{1},i_{2},\ldots,i_{r}$. In this case draw a cycle with edges $v_{j}v_{i_{1}},v_{i_{1}}v_{i_{2}},v_{i_{2}}v_{i_{3}},\ldots,v_{i_{r-1}}v_{i_{r}},v_{i_{r}}v_{j}$ as in Fig. 3 (right).

d) If three or more polygons $Q_{i_{1}},Q_{i_{2}},\ldots,Q_{i_{r}}$ share a vertex $p$ and $p$ is not a point of any polygon $Q_{k}$ other than $Q_{i_{1}},Q_{i_{2}},\ldots,Q_{i_{r}}$, then there is a neighbourhood $N$ of $p$ containing no points of any polygon $Q_{k}$ with $k\neq i_{1},i_{2},\ldots,i_{r}$. In this case draw a cycle with edges $v_{i_{1}}v_{i_{2}},v_{i_{2}}v_{i_{3}},\ldots,v_{i_{r-1}}v_{i_{r}},v_{i_{r}}v_{1}$ as in Fig. 4 (left).

e) If two polygons $Q_{i}$ and $Q_{j}$ share a vertex $p$ and $p$ is not a point of any polygon in $\mathcal{R}$ other than $Q_{i}$ and $Q_{j}$, then draw an edge $v_{i}v_{j}$ through $p$ as in Fig. 4 (right).

f) For each free side $s$ of a polygon $Q_{i}$ add an edge $v_{i}v_{n+1}$ drawn through an interior of point $p$ in $s$.

Notice that edges of type f) are the only possible multiple edges of $G$. Therefore $G$ is a plane multigraph with $n+1$ vertices and $m\leq(3(n+1)-6)+(x_{2}+2x_{3})=(3n-3)+(x_{2}+2x_{3})$ edges, where for $i=2,3$, $x_{i}$ denotes the number of polygons in $\mathcal{Q}$ with $i$ free sides.

We say that an edge $e=v_{i}v_{j}$ of $G$ intersects a side $s$ of a polygon in $\mathcal{Q}$ if $e$ is drawn through either an interior point of $s$ or through a vertex of $s$. Each non free side among polygons in $\mathcal{Q}$ is intersected by at least one edge of $G$ of type a), b), c), d) or e) and each free side is intersected by an edge of type f). We claim that if an edge $v_{i}v_{j}$ of $G$ is of type e) then two of the 4 sides intersected by $v_{i}v_{j}$ are intersected by at least another edge of $G$.

Without loss of generality we assume the line supporting a side $s$ of $Q_{i}$ separates $Q_{i}$ and $Q_{j}$. Let $b$ be the other side of $Q_{i}$ incident in the common vertex $p$ of $Q_{i}$ and $Q_{j}$. Then side $b$ must contain a point of a polygon $Q_{k}$ other than $Q_{i}$ and $Q_{j}$, otherwise $b$ could be translated away from $Q_{i}$ in the direction orthogonal to $b$ which is not possible by the properties of $\mathcal{Q}$ (see Fig. 7). This means that side $b$ is intersected by an edge of $G$ other than edge $v_{i}v_{j}$.

Analogously a side $c\neq b$, incident with $t$, is intersected by an edge of $G$ other than $v_{i}v_{j}$. $\square$

Let $T$ denote the total number of sides among polygons in $\mathcal{Q}$. Also let $m$, $m_{e}$ and $m_{f}$ denote the number of edges of $G$, the number of edges of $G$ of type e) and the number of edges of $G$ of type f), respectively. Since polygons in $\mathcal{Q}$ contain at most 3 free edges, $m_{f}=x_{1}+2x_{2}+3x_{3}$, where for $i=1,2,3$ $x_{i}$ is the number of polygons in $Q$ containing $i$ free edges.

In order to bound the number of sides among polygons in $\mathcal{Q}$ we add the number of sides intersected by edges of $G$ and subtract the number of sides intersected by at least two edges of $G$ (2 sides for each edge of type e)). Considering that edges of types a), b), c), and d), intersect at most 3 sides; edges of type e) intersect 4 sides and edges of type f) intersect one side, we have:

∎

Let $\mathcal{R}=\{R_{1},R_{2},\ldots R_{n}\}$ be a collection of pairwise disjoint convex polygons satisfying conditions 1), 2) and 3) in Lemma 1 and let $\mathcal{L}=\{l_{1},l_{2},\ldots,l_{m}\}$ be the (multi)set of lines supporting the sides of each polygon in $\mathcal{R}$. We include $c$ copies of a line $l$ if $l$ supports sides of $c$ polygons in $\mathcal{R}$. Therefore we can associate a unique polygon $R_{i(k)}$ to each line $l_{k}\in\mathcal{L}$ such that a side of $R_{i(k)}$ is supported by $l_{k}$. For $k=1,2,\ldots,m$ let $H_{k}^{-}$ be the closed halfplane determined by $l_{k}$ that does not contain $R_{i(k)}$.

Define a bipartite graph $F$ with a vertex $v_{j}$ for each polygon $R_{j}\in\mathcal{R}$ and a vertex $w_{k}$ for each line $l_{k}\in\mathcal{L}$. Graph $F$ has an edge $v_{j}w_{k}$ if polygon $R_{j}$ is contained in $H_{k}^{-}$.

For each pair of polygons $R_{i},R_{j}$ there is at least one side $s$ of one of them such that the line supporting $s$ separates $R_{i}$ from $R_{j}$. Therefore graph $F$ has at least one edge for each pair $\{i,j\}$ with $1\leq i<j\leq n$. This implies that there is a vertex $w_{k}$ whose degree in $F$ is at least $\binom{n}{2}/m\geq\binom{n}{2}/(9n-9)=n/18$.

This means that the line $l_{k}$ separates polygon $R_{i(k)}$ from at least $n/18$ polygons in $\mathcal{R}$. By Property 2) in Lemma 1, line $l_{k}$ supports a side of polygon $P_{i(k)}$.

∎

Let $n\geq 2$ be an integer and $\mathcal{C}=\{C_{1},C_{2},\ldots,C_{n}\}$ be a collection of pairwise disjoint compact convex sets in the plane and let $T$ be a triangle containing all sets in $\mathcal{C}$ in its interior.

For any line $l$ let $t_{l}^{-}$ and $t_{l}^{+}$ be the number of sets in $\mathcal{C}$ lying to the left and to the right of $l$, respectively; for a horizontal line $l$, $t_{l}^{-}$ and $t_{l}^{+}$ are the number of sets in $\mathcal{C}$ lying above and bellow $l$, respectively. For $1\leq i<j\leq n$ let $l_{ij}$ be a line separating $C_{i}$ from $C_{j}$ for which $max\{t_{l_{ij}}^{-},t_{l_{ij}}^{+}\}$ is as small as posible.

Each line $l_{ij}$ determines two closed halfplanes $H_{ij}$ and $H_{ji}$ containing $C_{i}$ and $C_{j}$, respectively. For $i=1,2,\ldots,n$, let $P_{i}=T\cap({\bigcap}_{j\neq i}^{n}H_{ij})$. Then For $i=1,2,\ldots,n$, $P_{i}$ is a convex polygon that contains set $C_{i}$ such that each side is supported by a line $l_{ij}$ or by a side of $T$.

Let $\mathcal{P}=\{P_{1},P_{2},\ldots,P_{n}\}$. By Lemma 2, there is a side $s$ of a polygon $P_{i}$ such that the line $l(s)$ supporting $s$ separates $P_{i}$ from a subcollection of $\mathcal{P}$ with at least $\frac{n}{18}$ polygons.

Since no side of $T$ separates polygons in $\mathcal{P}$, $l(s)$ is of the form $l_{ij}$. By the choice of $l_{ij}$ each line that separates sets $C_{i}$ from $C_{j}$ separates either $C_{i}$ or $C_{j}$ from at least $\frac{n}{18}$ sets in $\mathcal{C}$. ∎