9
$\begingroup$

Let $P$ be a convex $n$-gon ($n$ is odd and $n \geq 5$). Determine the smallest $m$ such that all edges and diagonals of $P$ can be covered by the edges of $m$ convex sub-polygons of $P$ which do not share any edges.

($Q$ is a sub-polygon of $P$ if all vertices of $Q$ are vertices of $P$).

This question was proposed at a Chinese contest and maybe it's a known result in graph theory.

For $n=5$, for example, it's not hard to see that $m(5)=3$. If $P:=P_{1}P_{2}P_{3}P_{4}P_{5}$, $m(5)=3$ can be achieved by 3 convex sub-polygons: $P_{1}P_{2}P_{4}P_{5}$; $P_{1}P_{3}P_{4}$; $P_{2}P_{3}P_{5}$. I also found that $m(7) \leq 6$, but I couldn't go further.

Any suggestion would be appreciated. Thanks in advance.

$\endgroup$
8
  • $\begingroup$ If it is a contest problem, maybe you may ask organizers or participants of the contest? $\endgroup$ Jul 18, 2015 at 15:42
  • $\begingroup$ @FedorPetrov Unfortunately this one took place in the early 90s. I'm not aware of any organizer/participant of this contest. $\endgroup$
    – jack
    Jul 18, 2015 at 15:58
  • $\begingroup$ Must $m\lt n$ hold, or is $m\le n$ also possible? $\endgroup$ Jul 19, 2015 at 7:45
  • $\begingroup$ @ManfredWeis There are no restrictions on $m$, except it has to be the smallest possible. So $m \leq n$ is also possible. $\endgroup$
    – jack
    Jul 19, 2015 at 14:57
  • $\begingroup$ I deleted my comment because I thought diagonals were also not to be shared. However, I thought a sub-polygon of a convex polygon was also convex (I guess vertex order matters?). There may still be a design interpretation, but my original one does not quite capture the problem. Gerhard "Thinks This Still Isn't Geometry" Paseman, 2015.07.19 $\endgroup$ Jul 19, 2015 at 23:15

2 Answers 2

8
$\begingroup$

Here's a lower bound that heynongman and I worked out. (This was previously posted with equality, but there was a flaw in the argument.) This is assuming that the diagonals (as well as the edges) of $P$ are not to be shared among the sub-polygons.

Suppose that the edges and diagonals of $P$ can be covered by $m$ convex sub-polygons $Q_1$, $Q_2$, ..., $Q_m$, having $a_1$, $a_2$, ..., $a_m$ edges, respectively. We want to cover $n\choose2$ edges and diagonals in all, so

$$a_1+a_2+\cdots+a_m={n\choose2}.\tag{1}$$

We define the cost $c(e)$ of an edge $e$ of $P$ (around the perimeter) to be 0, and the cost $c(e)$ of a diagonal $e$ to be the smallest number of intermediate vertices of $P$ in a path along the perimeter of $P$ from one endpoint to the other. For example, for $n=7$ and $P=P_1P_2P_3P_4P_5P_6P_7$, the cost of the diagonal $P_2P_6$ is 2 (because the shortest path around the perimeter between the endpoints is $P_6P_7P_1P_2$, which has two intermediate vertices). Intuitively, the cost of a diagonal is the minimum number of vertices of $P$ that must be "skipped" by a sub-polygon $Q_i$ that uses that diagonal, traversing the vertices of $Q_i$ clockwise.

The maximum cost of a diagonal is $(n-3)/2$. At each vertex, because $n$ is odd, there are exactly two diagonals of each cost from 1 to $(n-3)/2$, so the total cost of diagonals incident upon a given vertex is $2\sum_{i=1}^{(n-3)/2}i=(n-1)(n-3)/4$. If we sum over all vertices, we count the cost of each diagonal twice, so the sum of the costs of all edges and diagonals of $P$ is

$$ \sum_{e\in P}c(e)={n\over2}\left[(n-1)(n-3)\over4\right]. $$

Now, for any sub-polygon $Q_i$, every vertex of $P$ is either a vertex of $Q_i$ or is "skipped" by $Q_i$. The total cost of the edges of $Q_i$, $\sum_{e\in Q_i}c(e)$, is a lower bound on the number $n-a_i$ of "skipped" vertices, which is to say that $n-a_i\ge\sum_{e\in Q_i}c(e)$. (Our previous post claimed that $\sum_{e\in Q_i}c(e)=n-a_i$, but this is not necessarily true, because a sub-polygon may lie entirely in "one half" of $P$.) Therefore,

$$(n-a_1)+(n-a_2)+\cdots+(n-a_m)\ge\sum_{i=1}^m\sum_{e\in Q_i}c(e)=\sum_{e\in P}c(e)={n(n-1)(n-3)\over8}.\tag{2}$$

Adding (1) and (2), we get

$$mn\ge{n\choose2}+{n(n-1)(n-3)\over8}={n(n-1)(n+1)\over8},$$

so $m\ge(n-1)(n+1)/8$.

This lower bound gives $m(5)\ge3$, $m(7)\ge6$, and $m(9)\ge10$. We have constructions that meet this bound for $n=5,7,9$, but we don't have a general construction.

$\endgroup$
2
$\begingroup$

I think the following construction realizes the lower bound in Brian's answer. Let $n=2k+1$ and label the first $2k$ vertices with $\mathbb{Z}_{2k}=\{0,\ldots,2k-1\}$ and the last vertex with $\infty$. First we take all the $(n-1)(n-3)/8=2k(k-1)/4$ 4-gons of the form \[(i,\,i+j,\,i+k,\,i+k+j)\] with $i\in\{0,\ldots,2k-1\}$ and $j\in\{1,\ldots,k-1\}$. That covers everything not involving $\infty$ except the "long" diagonals $(i,i+k)$, so we add $(n-1)/2=k$ triangles $(i,i+k,\infty)$ for $i\in\{0,\ldots,k-1\}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.