Finding a Quadrilateral for N Points
Moderators: gmalivuk, Moderators General, Prelates

 Posts: 895
 Joined: Fri Feb 07, 2014 3:15 pm UTC
Finding a Quadrilateral for N Points
Given N coplanar points, no 3 of which are collinear, a quadrilateral can be drawn who's line segments contain all points and do not cross each other. What is the largest value N can have?
Re: Finding a Quadrilateral for N Points
Hint for an upper bound: each line segment of the quadrilateral contains at most 2 of the points.
Last edited by Demki on Thu Oct 20, 2016 6:45 pm UTC, edited 2 times in total.

 Posts: 35
 Joined: Wed Sep 24, 2014 5:01 pm UTC
Re: Finding a Quadrilateral for N Points
Clearly each edge can contain a maximum of two points, so you can't do better than 8. Given any quadrilateral, it's trivial to pick two noncorner points from each edge to obtain a qualifying collection of 8 points that way, and given the eight vertices of a convex octagon, you can extend out alternating sides until they intersect to turn it into a quadrilateral.

 Posts: 895
 Joined: Fri Feb 07, 2014 3:15 pm UTC
Re: Finding a Quadrilateral for N Points
curiosityspoon wrote:Given any quadrilateral, it's trivial to pick two noncorner points from each edge to obtain a qualifying collection of 8 points that way, and given the eight vertices of a convex octagon, you can extend out alternating sides until they intersect to turn it into a quadrilateral.
I think you did the problem backwards. First the points are selected, and then the polygon must be drawn.
 gmalivuk
 GNU Terry Pratchett
 Posts: 26413
 Joined: Wed Feb 28, 2007 6:02 pm UTC
 Location: Here and There
 Contact:
Re: Finding a Quadrilateral for N Points
jewish_scientist wrote:curiosityspoon wrote:Given any quadrilateral, it's trivial to pick two noncorner points from each edge to obtain a qualifying collection of 8 points that way, and given the eight vertices of a convex octagon, you can extend out alternating sides until they intersect to turn it into a quadrilateral.
I think you did the problem backwards. First the points are selected, and then the polygon must be drawn.
Yes, "given the eight verticies of a convex octagon" means the points are selected first.
Re: Finding a Quadrilateral for N Points
Those points are not arbitrary. If you're given a nonconvex set of points, things get messy.
I have no proof, but a bit of doodling suggests that N=5 may be possible in the general case (read: I found no counterexample), but N=6 is not (read: I found no obvious way to draw a quadrilateral on this set of points).
I have no proof, but a bit of doodling suggests that N=5 may be possible in the general case (read: I found no counterexample), but N=6 is not (read: I found no obvious way to draw a quadrilateral on this set of points).
 gmalivuk
 GNU Terry Pratchett
 Posts: 26413
 Joined: Wed Feb 28, 2007 6:02 pm UTC
 Location: Here and There
 Contact:
Re: Finding a Quadrilateral for N Points
The question wasn't clear. Some appropriate sets of 8 points *can* give a quadrilateral, while no set of 9 points works. which is a possible reading of the OP.
 doogly
 Dr. The Juggernaut of Touching Himself
 Posts: 5393
 Joined: Mon Oct 23, 2006 2:31 am UTC
 Location: Somerville, MA
 Contact:
Re: Finding a Quadrilateral for N Points
I feel good about 5, since you can get a quadratic curve to go through them. I feel like maybe you could finesse this proof? I have a good feeling about five.
LE4dGOLEM: What's a Doug?
Noc: A larval Doogly. They grow the tail and stinger upon reaching adulthood.
Keep waggling your butt brows Brothers.
Or; Is that your eye butthairs?
Noc: A larval Doogly. They grow the tail and stinger upon reaching adulthood.
Keep waggling your butt brows Brothers.
Or; Is that your eye butthairs?
Re: Finding a Quadrilateral for N Points
I think I have a construction for N=5 which always works. If the points are convex, it's easy. Otherwise, pick both points that are not on the convex hull (if there's only one, add a random other point), draw a line through both. You have three lines and three (convex) points remaining, and I think there's enough degrees of freedom that you can always catch one point with each line.
For N=6, draw two equilateral triangles inside each other, like so
Ignoring the sides, you now have 6 points. The symmetry makes bruteforcing possible.
We know that at least two sides of the polygon must touch two points each, which means that at least one of the outer points must share a side with another point. Minus symmetry, there's only three candidates that can share the side, and none of them seems to work out.
For N=6, draw two equilateral triangles inside each other, like so
Code: Select all
/\
/ \
/ /\ \
/ /__\ \
/________\
Ignoring the sides, you now have 6 points. The symmetry makes bruteforcing possible.
We know that at least two sides of the polygon must touch two points each, which means that at least one of the outer points must share a side with another point. Minus symmetry, there's only three candidates that can share the side, and none of them seems to work out.

 Posts: 895
 Joined: Fri Feb 07, 2014 3:15 pm UTC
Re: Finding a Quadrilateral for N Points
I actually have what I think is a clever proof for N=5.
I have been working on various versions of N=6. Right now the one I am stuck on is where ABCD is a rectangle and ABE is a right triangle that has translation symmetry with CDF.
I do not understand this proof. Can you please explain it again?
Spoiler:
I have been working on various versions of N=6. Right now the one I am stuck on is where ABCD is a rectangle and ABE is a right triangle that has translation symmetry with CDF.
Tub wrote:For N=6, draw two equilateral triangles inside each other, like soCode: Select all
/\
/ \
/ /\ \
/ /__\ \
/________\
Ignoring the sides, you now have 6 points. The symmetry makes bruteforcing possible.
We know that at least two sides of the polygon must touch two points each, which means that at least one of the outer points must share a side with another point. Minus symmetry, there's only three candidates that can share the side, and none of them seems to work out.
I do not understand this proof. Can you please explain it again?
Re: Finding a Quadrilateral for N Points
It's meant to be a counterexample. I've given you 6 points (the vertices of both triangles), try solving it. The symmetry of the points should make it easy to systematically check all possible solutions.
 Soupspoon
 You have done something you shouldn't. Or are about to.
 Posts: 3375
 Joined: Thu Jan 28, 2016 7:00 pm UTC
 Location: 531
Re: Finding a Quadrilateral for N Points
jewish_scientist wrote:I do not understand this proof. Can you please explain it again?
By my understanding, call the three outer triangle vertices A B C and internal (equivalent) a b c. Four linesegments passing through all six points must have two lines through two points, two through one.
The paired points cannot be two of (A a) (B b) or (C c):
1) if the two paired lines are adjacent (line ends touch at centre) the trailing 'onepoint lines' (from any point outside or on the A, B or C) seemingly cannot pass through one (each) of the remaining pointpair and meet to close the quadrilateral, without crossing;
2) if the paired lines are nonadjacent, i.e. opposite each other in a renormalised square version, at least one of the intermediate onepointers seems not to be posdible...
If just one pairing, say (A a), is used for a line then:
3) If (B c) or (C b) is the other double, and (visually) I can't see a way of connecting those (as adjacent or opposite lines) into a circuit by going through the remaining points and noncrossing.
4) If the other double is (B C) or (b c) then likewise.
If there are no pairings, then we're looking at both being (B c)ish and/or (B C)/(b c)ish pairings, as per 3 and 4's 'second pair', above  but obviously in mutually exclusive versions of the pair*), and all ways that I've played with in my head come out similarly stymied manner.
But I'd need to scribble on paper to be sure I've gotten every version, especially on the last lot of many combinations, where extra 'thinking outside the box' might reveal something I've missed. It looks like an exhsustively proved antiexample for 6 points, though.
(As Tub wrote, whilst I was writing this.)
* If two pairs share a point, by joining at a triangle vertex, then a third line has to be double, too, as the first two have 3 points for two lines, leaving 3 points (2+1 or 2+2 with one shared) for the opposite lines
 gmalivuk
 GNU Terry Pratchett
 Posts: 26413
 Joined: Wed Feb 28, 2007 6:02 pm UTC
 Location: Here and There
 Contact:
Re: Finding a Quadrilateral for N Points
jewish_scientist: your proof for N=5 isn't complete, because it's possible there is no side with angles adding to more than 180 that isn't part of a concave section. (Consider, for example, two points in the interior of the equilateral triangle formed by the other three points. None of the internal angles are between 90 and 180 degrees.)

 Posts: 895
 Joined: Fri Feb 07, 2014 3:15 pm UTC
Re: Finding a Quadrilateral for N Points
Yeah, I realized an hour or two after I posted that my proof did not work because ABCD could be a rectangle that E is inside. Fortunately, I have another proof.
EDIT: Never mind. I just found a problem with that one too. However, I am confident that a proof must exist for N=5, if for no other reason than I have been successful with N=6 so many times.
EDIT: Never mind. I just found a problem with that one too. However, I am confident that a proof must exist for N=5, if for no other reason than I have been successful with N=6 so many times.
 el matematico
 Posts: 113
 Joined: Mon Oct 19, 2009 12:20 pm UTC
Re: Finding a Quadrilateral for N Points
This reminds me of the happy ending problem https://en.wikipedia.org/wiki/Happy_ending_problem. Maybe start from there and look for similar theorems?
This is my blog (in Spanish). It's not perfect, but it's mine. http://falaci.blogspot.com/
 gmalivuk
 GNU Terry Pratchett
 Posts: 26413
 Joined: Wed Feb 28, 2007 6:02 pm UTC
 Location: Here and There
 Contact:
Re: Finding a Quadrilateral for N Points
In that case, just draw rays from E through A and B, then pick a point F far enough from CD that the rays FC and FD intersect EA and EB.jewish_scientist wrote:Yeah, I realized an hour or two after I posted that my proof did not work because ABCD could be a rectangle that E is inside.

 Posts: 895
 Joined: Fri Feb 07, 2014 3:15 pm UTC
Re: Finding a Quadrilateral for N Points
I know that solution; what I was upset about was that my proof was flawed. I just came up with a new proof though.
EDIT: Never mind, again. I thought of a problem with that proof to. This is so infuriating. I KNOW that there is a proof for N=5 and that I can find it, it just keeps slipping away. At this point, its personal; math has insulted my honor as a nerd and I will have my vengeance.
Spoiler:
EDIT: Never mind, again. I thought of a problem with that proof to. This is so infuriating. I KNOW that there is a proof for N=5 and that I can find it, it just keeps slipping away. At this point, its personal; math has insulted my honor as a nerd and I will have my vengeance.
Last edited by jewish_scientist on Thu Oct 27, 2016 2:00 pm UTC, edited 1 time in total.
Re: Finding a Quadrilateral for N Points
For N=5, I think it works if we divide into cases based on the number S of sides of the convex hull of the points.
For S=5
For S=4
For S=3
S=2 would imply all points are colinear, contrary to the initial problem statement.
For S=5
Spoiler:
For S=4
Spoiler:
For S=3
Spoiler:
S=2 would imply all points are colinear, contrary to the initial problem statement.

 Posts: 895
 Joined: Fri Feb 07, 2014 3:15 pm UTC
Re: Finding a Quadrilateral for N Points
I think you made a mistake. You said S is the number of sides of the concave areas and then said S=4. Since it is impossible for a concave area to be made out of 1 side, I am pretty sure you meant S to be the number of concave points. Also, can you prove that when N=5 it is impossible to form two different pentagon, each with a different concave point. I am not sure if this is necessary for your proof, but it cannot hurt to double check.
On a different subject, I am REALLY close to finishing a proof for N=5. I have the construction all worked out, I just cannot figure out how to explain it. Is there a shorter way to say, "If ray AB intersects ray CD AND ray AB does not intersect line segment CD except at point C or point D AND ray CD does not intersect line segment AB except at point A or point B, then label the point where ray AB and ray CD intersect X?" When AB and CD are possible sides of the quadrilateral, this statement comes up a lot.
On a different subject, I am REALLY close to finishing a proof for N=5. I have the construction all worked out, I just cannot figure out how to explain it. Is there a shorter way to say, "If ray AB intersects ray CD AND ray AB does not intersect line segment CD except at point C or point D AND ray CD does not intersect line segment AB except at point A or point B, then label the point where ray AB and ray CD intersect X?" When AB and CD are possible sides of the quadrilateral, this statement comes up a lot.

 Posts: 35
 Joined: Wed Sep 24, 2014 5:01 pm UTC
Re: Finding a Quadrilateral for N Points
No, it said nothing about the number of sides of any "concave areas" or "concave points", it defined S as the number of points which reside at vertices of the convex hull. Any collection of points will have exactly one convex hull, by the method which constructs a convex hull.
In particular, in 2dimensional space with a finite collection of points, the convex hull can be visualized by drawing the complete graph on all those points and looking at the outer boundary.
In particular, in 2dimensional space with a finite collection of points, the convex hull can be visualized by drawing the complete graph on all those points and looking at the outer boundary.

 Posts: 895
 Joined: Fri Feb 07, 2014 3:15 pm UTC
Re: Finding a Quadrilateral for N Points
I feel like an idiot now. When I read your proof I kept replacing 'convex' with 'concave.' Sorry.
Who is online
Users browsing this forum: No registered users and 9 guests