Finding a Quadrilateral for N Points

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

jewish_scientist
Posts: 936
Joined: Fri Feb 07, 2014 3:15 pm UTC

Finding a Quadrilateral for N Points

Postby jewish_scientist » Thu Oct 20, 2016 5:22 pm UTC

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?
"You are not running off with Cow-Skull Man Dracula Skeletor!"
-Socrates

Demki
Posts: 199
Joined: Fri Nov 30, 2012 9:29 pm UTC

Re: Finding a Quadrilateral for N Points

Postby Demki » Thu Oct 20, 2016 6:41 pm UTC

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.

curiosityspoon
Posts: 35
Joined: Wed Sep 24, 2014 5:01 pm UTC

Re: Finding a Quadrilateral for N Points

Postby curiosityspoon » Thu Oct 20, 2016 6:44 pm UTC

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 non-corner 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.

jewish_scientist
Posts: 936
Joined: Fri Feb 07, 2014 3:15 pm UTC

Re: Finding a Quadrilateral for N Points

Postby jewish_scientist » Tue Oct 25, 2016 1:01 pm UTC

curiosityspoon wrote:Given any quadrilateral, it's trivial to pick two non-corner 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.
"You are not running off with Cow-Skull Man Dracula Skeletor!"
-Socrates

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 26518
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: Finding a Quadrilateral for N Points

Postby gmalivuk » Tue Oct 25, 2016 3:09 pm UTC

jewish_scientist wrote:
curiosityspoon wrote:Given any quadrilateral, it's trivial to pick two non-corner 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.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

Tub
Posts: 399
Joined: Wed Jul 27, 2011 3:13 pm UTC

Re: Finding a Quadrilateral for N Points

Postby Tub » Tue Oct 25, 2016 3:23 pm UTC

Those points are not arbitrary. If you're given a non-convex 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).

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 26518
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: Finding a Quadrilateral for N Points

Postby gmalivuk » Tue Oct 25, 2016 3:32 pm UTC

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.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
doogly
Dr. The Juggernaut of Touching Himself
Posts: 5448
Joined: Mon Oct 23, 2006 2:31 am UTC
Location: Lexington, MA
Contact:

Re: Finding a Quadrilateral for N Points

Postby doogly » Tue Oct 25, 2016 3:32 pm UTC

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?

Tub
Posts: 399
Joined: Wed Jul 27, 2011 3:13 pm UTC

Re: Finding a Quadrilateral for N Points

Postby Tub » Wed Oct 26, 2016 11:33 am UTC

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

Code: Select all

    /\
   /  \
  / /\ \
 / /__\ \
/________\

Ignoring the sides, you now have 6 points. The symmetry makes brute-forcing 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.

jewish_scientist
Posts: 936
Joined: Fri Feb 07, 2014 3:15 pm UTC

Re: Finding a Quadrilateral for N Points

Postby jewish_scientist » Wed Oct 26, 2016 12:28 pm UTC

I actually have what I think is a clever proof for N=5.

Spoiler:
First, draw the pentagon ABCDE. Next, pick a side that is not part of a concave section and who's angles add up to more than 180o. Then extend the two line segments that share a vertex with this side until they intersect. I know that they must eventually intersect because that is Euclid's 5th axiom (I feel really awesome citing that in a proof I made). If you ignore the line segment originally selected, the sides of the resulting quadrilateral contains all the necessary points.


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 so

Code: Select all

    /\
   /  \
  / /\ \
 / /__\ \
/________\

Ignoring the sides, you now have 6 points. The symmetry makes brute-forcing 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?
"You are not running off with Cow-Skull Man Dracula Skeletor!"
-Socrates

Tub
Posts: 399
Joined: Wed Jul 27, 2011 3:13 pm UTC

Re: Finding a Quadrilateral for N Points

Postby Tub » Wed Oct 26, 2016 12:55 pm UTC

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.

User avatar
Soupspoon
You have done something you shouldn't. Or are about to.
Posts: 3643
Joined: Thu Jan 28, 2016 7:00 pm UTC
Location: 53-1

Re: Finding a Quadrilateral for N Points

Postby Soupspoon » Wed Oct 26, 2016 1:16 pm UTC

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 line-segments 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 'one-point lines' (from any point outside or on the A, B or C) seemingly cannot pass through one (each) of the remaining point-pair and meet to close the quadrilateral, without crossing;
2) if the paired lines are non-adjacent, i.e. opposite each other in a renormalised square version, at least one of the intermediate one-pointers 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 non-crossing.
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 anti-example 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

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 26518
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: Finding a Quadrilateral for N Points

Postby gmalivuk » Wed Oct 26, 2016 2:23 pm UTC

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.)
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

jewish_scientist
Posts: 936
Joined: Fri Feb 07, 2014 3:15 pm UTC

Re: Finding a Quadrilateral for N Points

Postby jewish_scientist » Wed Oct 26, 2016 5:29 pm UTC

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.
"You are not running off with Cow-Skull Man Dracula Skeletor!"
-Socrates

User avatar
el matematico
Posts: 113
Joined: Mon Oct 19, 2009 12:20 pm UTC

Re: Finding a Quadrilateral for N Points

Postby el matematico » Wed Oct 26, 2016 7:18 pm UTC

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/

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 26518
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: Finding a Quadrilateral for N Points

Postby gmalivuk » Wed Oct 26, 2016 7:46 pm UTC

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.
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.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

jewish_scientist
Posts: 936
Joined: Fri Feb 07, 2014 3:15 pm UTC

Re: Finding a Quadrilateral for N Points

Postby jewish_scientist » Wed Oct 26, 2016 9:01 pm UTC

I know that solution; what I was upset about was that my proof was flawed. I just came up with a new proof though.

Spoiler:
Label the given points such that ray AB intersects ray CD (label the point that they intersect X) and point E is within* angle AXC. The quadrilateral AXCE contains all the necessary points and has no sides that cross.

*By 'within', I mean that the sum of AXE and CXE is equal to AXC.


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.
"You are not running off with Cow-Skull Man Dracula Skeletor!"
-Socrates

DavidSh
Posts: 143
Joined: Thu Feb 25, 2016 6:09 pm UTC

Re: Finding a Quadrilateral for N Points

Postby DavidSh » Fri Oct 28, 2016 4:50 pm UTC

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
Spoiler:
you should always be able to remove one side and extend two adjacent sides to meet, forming a quadrilateral. A detailed argument could involve the total exterior angles of a pentagon.

For S=4
Spoiler:
Labeling the four points on the exterior in order around the boundary A, B, C, and D, and the interior point E, you can draw lines E-A-P and E-B-Q, with P and Q sufficiently far out that P-D and Q-C intersect at a point R, with (E-A-P), (P-D-R), (R-C-Q), (Q-B-E) forming a non-self-intersecting quadrilateral. How far out P and Q have to be depends on the relative distances of A-B and C-D.

For S=3
Spoiler:
Label the two interior points A and B. The line A-B intersects two of the sides of the triangle formed by the remaining three points. Label these points so the the intersection nearer A is on the side C-D, and the intersection nearer B is on side D-E.
Then the lines C-A and E-B intersect within the triangle, at some point P. Then (P-A-C), (C-D), (D-E), (E-B-P) forms a non-self-intersecting quadrilateral.

S=2 would imply all points are co-linear, contrary to the initial problem statement.

jewish_scientist
Posts: 936
Joined: Fri Feb 07, 2014 3:15 pm UTC

Re: Finding a Quadrilateral for N Points

Postby jewish_scientist » Mon Oct 31, 2016 1:15 am UTC

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.
"You are not running off with Cow-Skull Man Dracula Skeletor!"
-Socrates

curiosityspoon
Posts: 35
Joined: Wed Sep 24, 2014 5:01 pm UTC

Re: Finding a Quadrilateral for N Points

Postby curiosityspoon » Mon Oct 31, 2016 2:39 am UTC

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 2-dimensional 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.

jewish_scientist
Posts: 936
Joined: Fri Feb 07, 2014 3:15 pm UTC

Re: Finding a Quadrilateral for N Points

Postby jewish_scientist » Mon Oct 31, 2016 4:16 pm UTC

I feel like an idiot now. When I read your proof I kept replacing 'convex' with 'concave.' Sorry. :oops:
"You are not running off with Cow-Skull Man Dracula Skeletor!"
-Socrates


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 7 guests