This is a followup to my last question - Can we prove that simple polygons can always be split in half (vertex-wise) by diagonals?

Is there a constant natural number K for which the following is true:

For any simple polygon with more than 3 vertices there always exists a diagonal which:

  • is inside the polygon
  • doesn't intersect with any edges
  • splits the polygon in two polygons in such a way that the difference between their vertex counts is smaller than K
  • 1
    $\begingroup$ No, by a slight modification of the example answering the previous question: just place most of the vertices evenly between A and A' and the other two pairs. Gerhard "Imagine Using A Circular Saw Blade" Paseman, 2019.10.02. $\endgroup$ – Gerhard Paseman Oct 2 at 17:01

The answer is no, by modifying the answer to the previous question.

We start with an equilateral triangle $ABC$ and a larger equilateral triangle $A'B'C'$ with the same center and parallel edges. We consider the hexagon $AA'BB'CC'$.

enter image description here

Instead of this hexagon, we replace $A'$ with a sequence of $2K$ points all clustered near the original $A'$. Then we do the same for $B'$ and $C'$, so that the new polygon has $6K+3$ vertices.

Any division of this polygon into nearly equal halves will have to divide up one the clusters of $2K$ vertices. But starting from the cluster of vertices near $A'$, the only diagonals that avoid edges either stay within the cluster or go to $B$, so no diagonals can avoid the edges and provide the desired split.

  • $\begingroup$ What's the minimum difference between halves achievable in this polygon? $\endgroup$ – Dorijan Cirkveni Oct 2 at 17:15
  • $\begingroup$ A diagonal from $A$ to $B$ has $2K$ vertices on one side, $4K+1$ on the other, so the minimum difference (which I think is what you meant to say) is $2K+1$. $\endgroup$ – Matt F. Oct 2 at 17:15
  • $\begingroup$ Yes, that is what I meant to say. I changed my comment accordingly. $\endgroup$ – Dorijan Cirkveni Oct 2 at 17:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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