Can the boundaries of two pentagons intersect at $20$ points?

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP











up vote
16
down vote

favorite
8












This question is a follow-up to Maximum number of intersections between a quadrilateral and a pentagon, where it is shown that the boundaries $partial Q,partial P$ of a quadrilateral and a pentagon in the plane cannot intersect at more than $16$ points, since each side of $partial Q$ meets $partial P$ at an even number of points.




Q: Given the boundaries $partial P_1, partial P_2$ of two pentagons in
the plane, is it possible that $$ left|partial P_1 cap partial P_2
right| = 20?$$




Each side of $partial P_1$ meets $partial P_2$ at an even number of points, so equality is attained iff there is some configuration such that each side of $partial P_1$ meets each side of $partial P_2$ except one. $left|partial P_1 cap partial P_2right| = 18$ is possible, as shown below,
enter image description here



and I believe that $left|partial P_1 cap partial P_2right| = 20$ is impossible, but I am failing to prove it.







share|cite|improve this question























    up vote
    16
    down vote

    favorite
    8












    This question is a follow-up to Maximum number of intersections between a quadrilateral and a pentagon, where it is shown that the boundaries $partial Q,partial P$ of a quadrilateral and a pentagon in the plane cannot intersect at more than $16$ points, since each side of $partial Q$ meets $partial P$ at an even number of points.




    Q: Given the boundaries $partial P_1, partial P_2$ of two pentagons in
    the plane, is it possible that $$ left|partial P_1 cap partial P_2
    right| = 20?$$




    Each side of $partial P_1$ meets $partial P_2$ at an even number of points, so equality is attained iff there is some configuration such that each side of $partial P_1$ meets each side of $partial P_2$ except one. $left|partial P_1 cap partial P_2right| = 18$ is possible, as shown below,
    enter image description here



    and I believe that $left|partial P_1 cap partial P_2right| = 20$ is impossible, but I am failing to prove it.







    share|cite|improve this question





















      up vote
      16
      down vote

      favorite
      8









      up vote
      16
      down vote

      favorite
      8






      8





      This question is a follow-up to Maximum number of intersections between a quadrilateral and a pentagon, where it is shown that the boundaries $partial Q,partial P$ of a quadrilateral and a pentagon in the plane cannot intersect at more than $16$ points, since each side of $partial Q$ meets $partial P$ at an even number of points.




      Q: Given the boundaries $partial P_1, partial P_2$ of two pentagons in
      the plane, is it possible that $$ left|partial P_1 cap partial P_2
      right| = 20?$$




      Each side of $partial P_1$ meets $partial P_2$ at an even number of points, so equality is attained iff there is some configuration such that each side of $partial P_1$ meets each side of $partial P_2$ except one. $left|partial P_1 cap partial P_2right| = 18$ is possible, as shown below,
      enter image description here



      and I believe that $left|partial P_1 cap partial P_2right| = 20$ is impossible, but I am failing to prove it.







      share|cite|improve this question











      This question is a follow-up to Maximum number of intersections between a quadrilateral and a pentagon, where it is shown that the boundaries $partial Q,partial P$ of a quadrilateral and a pentagon in the plane cannot intersect at more than $16$ points, since each side of $partial Q$ meets $partial P$ at an even number of points.




      Q: Given the boundaries $partial P_1, partial P_2$ of two pentagons in
      the plane, is it possible that $$ left|partial P_1 cap partial P_2
      right| = 20?$$




      Each side of $partial P_1$ meets $partial P_2$ at an even number of points, so equality is attained iff there is some configuration such that each side of $partial P_1$ meets each side of $partial P_2$ except one. $left|partial P_1 cap partial P_2right| = 18$ is possible, as shown below,
      enter image description here



      and I believe that $left|partial P_1 cap partial P_2right| = 20$ is impossible, but I am failing to prove it.









      share|cite|improve this question










      share|cite|improve this question




      share|cite|improve this question









      asked Mar 29 at 9:32









      Jack D'Aurizio♦

      270k31266630




      270k31266630




















          1 Answer
          1






          active

          oldest

          votes

















          up vote
          9
          down vote



          accepted










          According to Theorem 4 from Černy et al.'s "On the number of intersections of two polygons" (2003), the number of intersections is bounded by $$5times 5-leftlceil frac56 rightrceil-5=19$$
          Therefore $18$ is the maximum.



          Alternatively, Theorem 5 gives the exact value $4times 5-2=18$.



          These maximal intersection numbers are hard to compute when both polygons have an odd number of vertices. Otherwise there are general formulas given by Theorem 1 and 2.



          Edit: found a better result in Günther's "The maximum number of intersections of two polygons" (2012).




          Theorem: the maximal number of intersections between an $n$-polygon and an $m$-polygon with $n$ and $m$ both odd is $(n-1)(m-1)+2$.







          share|cite|improve this answer























          • (+1) Nice, essentially it is enough to study a few configurations, according to the number of vertices of the convex envelopes of $P_1$ and $P_2$. But I would be happier in having a proof independent from a case-by-case analysis.
            – Jack D'Aurizio♦
            Mar 29 at 10:20











          • @JackD'Aurizio I added a stronger result. I don't have time to have a look at the proof, but since it is general I guess that they found something more clever than a case by case analysis.
            – Arnaud Mortier
            Mar 29 at 10:25











          • Gunther's approach is more general and cleaner, indeed. Thanks for your contribution. $colorgreencheckmark$
            – Jack D'Aurizio♦
            Mar 29 at 10:28










          • @JackD'Aurizio You're very welcome.
            – Arnaud Mortier
            Mar 29 at 10:31










          • @Rahul thanks for the edit.
            – Arnaud Mortier
            Mar 29 at 10:46










          Your Answer




          StackExchange.ifUsing("editor", function ()
          return StackExchange.using("mathjaxEditing", function ()
          StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
          StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
          );
          );
          , "mathjax-editing");

          StackExchange.ready(function()
          var channelOptions =
          tags: "".split(" "),
          id: "69"
          ;
          initTagRenderer("".split(" "), "".split(" "), channelOptions);

          StackExchange.using("externalEditor", function()
          // Have to fire editor after snippets, if snippets enabled
          if (StackExchange.settings.snippets.snippetsEnabled)
          StackExchange.using("snippets", function()
          createEditor();
          );

          else
          createEditor();

          );

          function createEditor()
          StackExchange.prepareEditor(
          heartbeatType: 'answer',
          convertImagesToLinks: true,
          noModals: false,
          showLowRepImageUploadWarning: true,
          reputationToPostImages: 10,
          bindNavPrevention: true,
          postfix: "",
          noCode: true, onDemand: true,
          discardSelector: ".discard-answer"
          ,immediatelyShowMarkdownHelp:true
          );



          );








           

          draft saved


          draft discarded


















          StackExchange.ready(
          function ()
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2713012%2fcan-the-boundaries-of-two-pentagons-intersect-at-20-points%23new-answer', 'question_page');

          );

          Post as a guest






























          1 Answer
          1






          active

          oldest

          votes








          1 Answer
          1






          active

          oldest

          votes









          active

          oldest

          votes






          active

          oldest

          votes








          up vote
          9
          down vote



          accepted










          According to Theorem 4 from Černy et al.'s "On the number of intersections of two polygons" (2003), the number of intersections is bounded by $$5times 5-leftlceil frac56 rightrceil-5=19$$
          Therefore $18$ is the maximum.



          Alternatively, Theorem 5 gives the exact value $4times 5-2=18$.



          These maximal intersection numbers are hard to compute when both polygons have an odd number of vertices. Otherwise there are general formulas given by Theorem 1 and 2.



          Edit: found a better result in Günther's "The maximum number of intersections of two polygons" (2012).




          Theorem: the maximal number of intersections between an $n$-polygon and an $m$-polygon with $n$ and $m$ both odd is $(n-1)(m-1)+2$.







          share|cite|improve this answer























          • (+1) Nice, essentially it is enough to study a few configurations, according to the number of vertices of the convex envelopes of $P_1$ and $P_2$. But I would be happier in having a proof independent from a case-by-case analysis.
            – Jack D'Aurizio♦
            Mar 29 at 10:20











          • @JackD'Aurizio I added a stronger result. I don't have time to have a look at the proof, but since it is general I guess that they found something more clever than a case by case analysis.
            – Arnaud Mortier
            Mar 29 at 10:25











          • Gunther's approach is more general and cleaner, indeed. Thanks for your contribution. $colorgreencheckmark$
            – Jack D'Aurizio♦
            Mar 29 at 10:28










          • @JackD'Aurizio You're very welcome.
            – Arnaud Mortier
            Mar 29 at 10:31










          • @Rahul thanks for the edit.
            – Arnaud Mortier
            Mar 29 at 10:46














          up vote
          9
          down vote



          accepted










          According to Theorem 4 from Černy et al.'s "On the number of intersections of two polygons" (2003), the number of intersections is bounded by $$5times 5-leftlceil frac56 rightrceil-5=19$$
          Therefore $18$ is the maximum.



          Alternatively, Theorem 5 gives the exact value $4times 5-2=18$.



          These maximal intersection numbers are hard to compute when both polygons have an odd number of vertices. Otherwise there are general formulas given by Theorem 1 and 2.



          Edit: found a better result in Günther's "The maximum number of intersections of two polygons" (2012).




          Theorem: the maximal number of intersections between an $n$-polygon and an $m$-polygon with $n$ and $m$ both odd is $(n-1)(m-1)+2$.







          share|cite|improve this answer























          • (+1) Nice, essentially it is enough to study a few configurations, according to the number of vertices of the convex envelopes of $P_1$ and $P_2$. But I would be happier in having a proof independent from a case-by-case analysis.
            – Jack D'Aurizio♦
            Mar 29 at 10:20











          • @JackD'Aurizio I added a stronger result. I don't have time to have a look at the proof, but since it is general I guess that they found something more clever than a case by case analysis.
            – Arnaud Mortier
            Mar 29 at 10:25











          • Gunther's approach is more general and cleaner, indeed. Thanks for your contribution. $colorgreencheckmark$
            – Jack D'Aurizio♦
            Mar 29 at 10:28










          • @JackD'Aurizio You're very welcome.
            – Arnaud Mortier
            Mar 29 at 10:31










          • @Rahul thanks for the edit.
            – Arnaud Mortier
            Mar 29 at 10:46












          up vote
          9
          down vote



          accepted







          up vote
          9
          down vote



          accepted






          According to Theorem 4 from Černy et al.'s "On the number of intersections of two polygons" (2003), the number of intersections is bounded by $$5times 5-leftlceil frac56 rightrceil-5=19$$
          Therefore $18$ is the maximum.



          Alternatively, Theorem 5 gives the exact value $4times 5-2=18$.



          These maximal intersection numbers are hard to compute when both polygons have an odd number of vertices. Otherwise there are general formulas given by Theorem 1 and 2.



          Edit: found a better result in Günther's "The maximum number of intersections of two polygons" (2012).




          Theorem: the maximal number of intersections between an $n$-polygon and an $m$-polygon with $n$ and $m$ both odd is $(n-1)(m-1)+2$.







          share|cite|improve this answer















          According to Theorem 4 from Černy et al.'s "On the number of intersections of two polygons" (2003), the number of intersections is bounded by $$5times 5-leftlceil frac56 rightrceil-5=19$$
          Therefore $18$ is the maximum.



          Alternatively, Theorem 5 gives the exact value $4times 5-2=18$.



          These maximal intersection numbers are hard to compute when both polygons have an odd number of vertices. Otherwise there are general formulas given by Theorem 1 and 2.



          Edit: found a better result in Günther's "The maximum number of intersections of two polygons" (2012).




          Theorem: the maximal number of intersections between an $n$-polygon and an $m$-polygon with $n$ and $m$ both odd is $(n-1)(m-1)+2$.








          share|cite|improve this answer















          share|cite|improve this answer



          share|cite|improve this answer








          edited Mar 29 at 10:46


























          answered Mar 29 at 10:15









          Arnaud Mortier

          19.2k22159




          19.2k22159











          • (+1) Nice, essentially it is enough to study a few configurations, according to the number of vertices of the convex envelopes of $P_1$ and $P_2$. But I would be happier in having a proof independent from a case-by-case analysis.
            – Jack D'Aurizio♦
            Mar 29 at 10:20











          • @JackD'Aurizio I added a stronger result. I don't have time to have a look at the proof, but since it is general I guess that they found something more clever than a case by case analysis.
            – Arnaud Mortier
            Mar 29 at 10:25











          • Gunther's approach is more general and cleaner, indeed. Thanks for your contribution. $colorgreencheckmark$
            – Jack D'Aurizio♦
            Mar 29 at 10:28










          • @JackD'Aurizio You're very welcome.
            – Arnaud Mortier
            Mar 29 at 10:31










          • @Rahul thanks for the edit.
            – Arnaud Mortier
            Mar 29 at 10:46
















          • (+1) Nice, essentially it is enough to study a few configurations, according to the number of vertices of the convex envelopes of $P_1$ and $P_2$. But I would be happier in having a proof independent from a case-by-case analysis.
            – Jack D'Aurizio♦
            Mar 29 at 10:20











          • @JackD'Aurizio I added a stronger result. I don't have time to have a look at the proof, but since it is general I guess that they found something more clever than a case by case analysis.
            – Arnaud Mortier
            Mar 29 at 10:25











          • Gunther's approach is more general and cleaner, indeed. Thanks for your contribution. $colorgreencheckmark$
            – Jack D'Aurizio♦
            Mar 29 at 10:28










          • @JackD'Aurizio You're very welcome.
            – Arnaud Mortier
            Mar 29 at 10:31










          • @Rahul thanks for the edit.
            – Arnaud Mortier
            Mar 29 at 10:46















          (+1) Nice, essentially it is enough to study a few configurations, according to the number of vertices of the convex envelopes of $P_1$ and $P_2$. But I would be happier in having a proof independent from a case-by-case analysis.
          – Jack D'Aurizio♦
          Mar 29 at 10:20





          (+1) Nice, essentially it is enough to study a few configurations, according to the number of vertices of the convex envelopes of $P_1$ and $P_2$. But I would be happier in having a proof independent from a case-by-case analysis.
          – Jack D'Aurizio♦
          Mar 29 at 10:20













          @JackD'Aurizio I added a stronger result. I don't have time to have a look at the proof, but since it is general I guess that they found something more clever than a case by case analysis.
          – Arnaud Mortier
          Mar 29 at 10:25





          @JackD'Aurizio I added a stronger result. I don't have time to have a look at the proof, but since it is general I guess that they found something more clever than a case by case analysis.
          – Arnaud Mortier
          Mar 29 at 10:25













          Gunther's approach is more general and cleaner, indeed. Thanks for your contribution. $colorgreencheckmark$
          – Jack D'Aurizio♦
          Mar 29 at 10:28




          Gunther's approach is more general and cleaner, indeed. Thanks for your contribution. $colorgreencheckmark$
          – Jack D'Aurizio♦
          Mar 29 at 10:28












          @JackD'Aurizio You're very welcome.
          – Arnaud Mortier
          Mar 29 at 10:31




          @JackD'Aurizio You're very welcome.
          – Arnaud Mortier
          Mar 29 at 10:31












          @Rahul thanks for the edit.
          – Arnaud Mortier
          Mar 29 at 10:46




          @Rahul thanks for the edit.
          – Arnaud Mortier
          Mar 29 at 10:46












           

          draft saved


          draft discarded


























           


          draft saved


          draft discarded














          StackExchange.ready(
          function ()
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2713012%2fcan-the-boundaries-of-two-pentagons-intersect-at-20-points%23new-answer', 'question_page');

          );

          Post as a guest













































































          這個網誌中的熱門文章

          How to combine Bézier curves to a surface?

          Mutual Information Always Non-negative

          Why am i infinitely getting the same tweet with the Twitter Search API?