8
$\begingroup$

You are given a convex polygon, ie all its internal angles are less than 180 degrees. Prove that you can always draw three straight lines through a specific point inside this polygon, such that they divide it into 6 equal (by area) regions? Bonus questions:

  • Can you prove that this can be achieved for non-convex polygons too? This time the point may not lie inside the polygon.
  • Does this result extend to 4 lines dividing a convex polygon into 8 equal regions?

This question was inspired by the hard problem in the recent TopCoder Open Algorithm final, written by Michal Forisek (misof).

$\endgroup$
0

1 Answer 1

Reset to default
2
$\begingroup$

Let's have a polygon. Let's draw a line at some angle $\theta_1$ to some fixed direction. By moving the line parallel to itself, we can make the whole polygon to lie either on one side of the line or the other. Thus, since the function “area on one side minus area on the another” is continuous, it should go through zero. Thus, for every $\theta_1$ there is a line $AD = L(\theta_1)$ that splits the polygon in halves.

Using the same mean value theorem we can show, that for every $\theta_1$, there is $\theta_2$ such that lines $L_1=AD=L(\theta_1)$ and $L_2=BE=L(\theta_2)$ split the area in a proportion $k=[APB]/[BPD]=1/2$. Indeed, if $\theta_2=\theta_1$, then $L_1=L_2$ and $k=0$. However, if $\theta_2=\theta_1+\pi$ (we rotated the line 2 by $\pi$ and $L_1=L_2$ again), then $k=\infty$. Given $k(\theta_2)$ is continuous, there should be some $\theta_2$, so $k=1/2$

By the same argument, for every $\theta_1$ there is always a $\theta_3$ and line $L_3=CF=L(\theta_3)$, so $k=[AQC]/[CQD]=2$.

enter image description here

Now consider point $R$, the intersection of $L_2$ and $L_3$. As we traverse from $\theta_1\to\theta_1+\pi$, lines $L2\leftrightarrow L3$ and $P\leftrightarrow Q$, but $R\to R$. However, now $R$ lies on the other side of line $L_1$. That means that during its journey, it crossed the line $L_1$. At this moment all three lines pass through one point.

By the way, we didn't use neither property of convexity, nor that it is a polygon. What mattered is that the area of the intersection of this shape with half-plane is continuous in respect to movements of the half-plane.

$\endgroup$
3
  • $\begingroup$ So how can we ensure the 'jorney' mentioned in paragraph 4 is continuous? $\endgroup$
    – user376921
    Nov 21, 2019 at 12:29
  • $\begingroup$ It takes several formalities, but it boils down to showing: 1) $L(\theta)$ is continuous (e.g, in terms of intersections with large circle); 2) $\theta_{2,3}(\theta_1)$ are continuous; 3) lines $L_2$ and $L_3$ are never coincident or parallel => $R(\theta_1)$ is a continuous motion $\endgroup$
    – Vasily Mitch
    Nov 21, 2019 at 12:34
  • $\begingroup$ In my understnading, 1) distance between $L(\theta)$ is taken to be supremum of distance between lines inside the polygon. 2) $\theta _2,\theta_3$ as output, are well-defined due to continuity of L under the metric, continuous since intuition (if $L$ close to $L(\theta_1)$, then $\theta_{2,3}(\theta_1) $ close to $ \theta_{2,3}(L)$ ). 3) $\theta _1 \rightarrow \theta _1 +\pi$ is just a flip in orientation, and $R(\theta _1) $ continuous as intuition. To add, since $ L(\theta)$ continuous as shown, the triplet $ (P,Q,R)$ is then continuous. So this triplet have equal entries in some $\theta$ $\endgroup$
    – user376921
    Nov 21, 2019 at 12:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .