Can the boundaries of two pentagons intersect at $20$ points?
Clash Royale CLAN TAG#URR8PPP
up vote
16
down vote
favorite
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,
and I believe that $left|partial P_1 cap partial P_2right| = 20$ is impossible, but I am failing to prove it.
combinatorics curves intersection-theory
add a comment |Â
up vote
16
down vote
favorite
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,
and I believe that $left|partial P_1 cap partial P_2right| = 20$ is impossible, but I am failing to prove it.
combinatorics curves intersection-theory
add a comment |Â
up vote
16
down vote
favorite
up vote
16
down vote
favorite
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,
and I believe that $left|partial P_1 cap partial P_2right| = 20$ is impossible, but I am failing to prove it.
combinatorics curves intersection-theory
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,
and I believe that $left|partial P_1 cap partial P_2right| = 20$ is impossible, but I am failing to prove it.
combinatorics curves intersection-theory
asked Mar 29 at 9:32
Jack D'Aurizioâ¦
270k31266630
270k31266630
add a comment |Â
add a comment |Â
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$.
(+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
add a comment |Â
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$.
(+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
add a comment |Â
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$.
(+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
add a comment |Â
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$.
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$.
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
add a comment |Â
(+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
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
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
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password