Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Angle Paralellograms

  1. Feb 11, 2006 #1

    0rthodontist

    User Avatar
    Science Advisor

    I was thinking about a problem on one of the old Putnam exams and as an aside started thinking about this: is it true that for any convex polygon of 5 or more sides, there exist 3 adjacent vertices A, B, C, such that if you "complete the parallelogram" for those 3 points, the fourth vertex of the parallelogram lies within the polygon?

    I came up with a mostly pictorial proof for quadrilaterals, though instead of ensuring that the fourth vertex of the parallelogram lies strictly within the quadrilateral, it might only fall at an edge or vertex of the quadrilateral.

    http://img226.imageshack.us/my.php?image=parall3qh.png

    In the top diagram, I have placed vertices A, B, C of the quadrilateral and drawn with dotted lines the completed parallelogram for A, B, C, whose fourth vertex I denote p(A, B, C). The fourth point D of the quadrilateral cannot lie within the upper red region without allowing p(A, B, C) to lie within the quadrilateral. And D cannot lie within the lower red region, because then p(C, D, A) would lie within the quadrilateral. If D lies on the boundaries of these regions (exactly on a dotted line) then p(A, B, C) or p(C, D, A) will lie on the boundary of the quadrilateral. But assume that neither p(A, B, C) nor p(C, D, A) lies on either the boundary of the quadrilateral or within the quadrilateral, and continue.

    WLOG, say that D lies on the left side of the red regions (if not, reflect the figure). Then as shown in the lower diagram, angle DAC equals angle u plus angle t, and angle ABC equals angle v plus angle u, with all of those angles greater than zero for reasons that can be seen by looking at parallel lines and the location of D. So angle u is strictly less than both angle DAC and angle ABC, and it follows that p(D, A, B) lies within the quadrilateral.

    So in a quadrilateral, of all the fourth vertices of parallelograms completed from three adjacent vertices of the quadrilateral, there must exist at least one that either lies on the boundary of the quadrilateral or within it.


    I don't know how or if I can use this to prove the case for polygons with more than 4 sides. Also, a lot of this proof sort of depends on geometric "eyeballing" which isn't as symbolic as I'd like, so maybe there is a clearer way to approach the problem. Any ideas?
     
    Last edited: Feb 11, 2006
  2. jcsd
  3. Feb 12, 2006 #2

    0rthodontist

    User Avatar
    Science Advisor

    Well, I figured out a way that satisfies me to prove that for every convex pentagon, there is an angle whose completed parallelogram contains a fourth point that is strictly within the pentagon. I am thinking I might want to turn this into a small project, to answer the question:

    For a convex polygon with n vertices, what is the minimum number of fourth points of angle parallelograms that lie within the polygon?

    Is this worth proving? Has someone already asked and answered this question? Where would I look to find out if they have?
     
    Last edited: Feb 12, 2006
  4. Feb 13, 2006 #3
    The answer is yes, it has been proven before. for any convex n polygon, there will be at least two triples of adjacent vertices whose ghost parallelogram vertex will lie within the polygon. This is a consequence of the discrete version of the 4-vertex theorem. That theorem states that there are at least 2 triples of vertices that define circles that are completely contained within the convex polygon. Since the 4th vertex of the parallelogram will necessarily lie within this circle, it also has to lie within the polygon.

    A recent reference for this is Tabachnikov and Ovsienko's paper on this:

    Projective geometry of polygons and discrete 4-vertex and 6-vertex theorems, with V. Ovsienko. L'Enseign. Math., 47 (2001), 3-19

    You can find a preprint here: http://www.math.psu.edu/tabachni/prints/preprints.html

    There's also a very elegant, slightly more elementary paper on the subject by Sedykh. It's referenced in the above paper.
     
  5. Feb 13, 2006 #4

    0rthodontist

    User Avatar
    Science Advisor

    Oh, ok. I don't have the background to understand that paper yet, but thanks for pointing me in the right direction.

    Do you mean for polygons with some specified larger number of vertices? The quadrilateral I linked to in the first post has only one ghost parallelogram vertex contained within the polygon.
     
    Last edited: Feb 13, 2006
  6. Feb 13, 2006 #5
    You're right. I think I might have spoken too soon. A better way to state the theorem -- or rather one of its consequences -- is: There are at least two pairs of vertices each of which generates a circle outside of which are the other vertices. However, it does not necessarily guarantee that the ghost parallelogram point of any of those triples lies within the polygon.

    Well, that approach was a bust...
     
  7. Feb 13, 2006 #6
    Ok, you've given me a problem that I'm now obsessing over. It seems to me that the key is to show it for quadrilaterals: that is, that there is at least one such point. Simple counting and making sure that you don't double-count will then give a (most likely not strict) lower bound for any convex n-gon.

    A reference that you might find useful is the "Quadrilaterals" chapter of Alfred Posamentier's text "Advanced Euclidean Geometry"
     
  8. Feb 13, 2006 #7

    0rthodontist

    User Avatar
    Science Advisor

    Well, I have no problem showing it for quadrilaterals. The approach of the first post yields the result that one of the following cases is true, dependent on the position of D:

    1. D lies fully outside the red regions (WLOG on the left). The quadrilateral has exactly 1 contained ghost parallelogram vertex.

    2. D lies on an edge of the upper red region. The quadrilateral has one edge that contains 2 ghost parallelogram vertices, and the other 2 are outside.

    3. D lies exactly on p(A, B, C). All four of the ghost parallelogram vertices coincide with the actual vertices of the quadrilateral.


    And 3 more cases each equivalent to one of those above:

    4. D lies within the upper red region. The quadrilateral has exactly 1 contained ghost parallelogram vertex. (This requires another diagram to verify) This is the same as case 1, with D, A, B, and A, B, C interchanged.

    5. D lies within the lower red region. This is the same as case 4 with A, B, C and C, D, B reversed.

    6. D lies on an edge of the lower red region. This is the same as case 2 with A, B, C and C, D, B reversed.


    I can show a less comprehensive result for convex pentagons using a different method, and I could probably extend the same method when I have a while.
     
  9. Feb 13, 2006 #8

    0rthodontist

    User Avatar
    Science Advisor

    Here is a proof that in any convex polygon, at most 3 fourth points of completed parallelograms on vertices may lie strictly outside the polygon:

    Assume otherwise, and say there are 4 vertices all of whose completed parallelograms' fourth points lie strictly outside the polygon. Join the four vertices to form a convex quadrilateral. Then the fourth points of ghost parallelograms for each vertex of this quadrilateral must lie strictly outside the quadrilateral, by a lemma I will support in a minute. But I have just shown that this is impossible in the post directly above, so by contradiction at most 3 fourth points of completed parallelograms may lie outside the polygon.

    This is a tight upper bound, because it is simple to construct a convex polygon with n sides with exactly 3 ghost parallelogram points outside. Just take a quadrilateral with exactly 3 ghost parallelogram points outside, and on the vertex whose ghost parallelogram point lies inside, split the vertex into n - 4 different convex sides which can be made to fit in as small a space as needed, thus preserving the exteriority of the 3 ghost parallelogram points.

    Now for the lemma mentioned above: If the ghost parallelogram point formed by A, B, C lies outside the polygon, and D is any other vertex of the polygon, then the ghost parallelogram point p(A, B, D) also lies outside the polygon. This lemma would clearly allow one to connect the four points as mentioned above while preserving ghost point exteriority.

    I'm actually having trouble proving this lemma, though I'm almost certain it's true.
     
    Last edited: Feb 13, 2006
  10. Feb 13, 2006 #9
    Problems with proving the lemma aside for now, the problem I have with your proof is that, in the original statement of the theorem, it does not seem to indicate that the 3 "fourth points" come from the only 4 vertices. It seems to me that there could be up to 12 vertices involved. That is, the contrapositive hypothesis would be: there are at least 4 "fourth points" living outside of the polygon, i.e. there are 4 triples of vertices such that their respective "fourth points" are not contained in the given polygon.
     
  11. Feb 13, 2006 #10

    0rthodontist

    User Avatar
    Science Advisor

    That's exactly how my proof proceeds... I'm not sure how you are interpreting it. If there are at least 4 fourth points, there must be a set of 4 specific fourth points I can check for inconsistency, which is what I did.

    Maybe I was unclear when I said "4 vertices all of whose completed parallelograms' fourth points...." What I mean by that is, 4 central vertices. So if A, B, C have a completed parallelogram with a fourth point outside the polygon, then I would say B has a completed parallelogram with a fourth point outside the polygon.

    Yes, on a second reading I'm pretty sure that's what you mean. So there could be up to 12 vertices involved but I am only looking at the central points of each triple.
     
    Last edited: Feb 13, 2006
  12. Feb 13, 2006 #11
    Ah... I understand now.
     
  13. Feb 13, 2006 #12
    I'm confused by this lemma vis-a-vis your conjecture. If we have say, a 37-gon, and vertices A,B, C such that p(A,B,C) lies outside of the polygon, then according to the lemma p(A,B,D) lives outside of the polygon too for any vertex of the 37-gon. That's 35 more exterior ghost points!

    Am I reading something wrong?
     
  14. Feb 13, 2006 #13

    0rthodontist

    User Avatar
    Science Advisor

    Well, because A, B, and D are not adjacent, their ghost parallelogram doesn't count.

    Here is a graphical proof of the lemma.
    http://img345.imageshack.us/my.php?image=geometry2cw.png

    I think the top two images explain themselves except to note that there are 2 areas in the top right that I am counting as Case 2. For the botton left picture, if D is in the Case 1 region, then p(A, B, D) is in the area wedged off by p(A, B, C). So if p(A, B, D) is in the polygon, then draw a line segment from p(A, B, D) through p(A, B, C) so that it passes the line AC. This segment has endpoints in the polygon at p(A, B, D) and at some point in triangle ABC, but it has a point along it, namely p(A, B, C), that is not in the polygon, contradicting the assumption that the polygon is convex.

    For the bottom right picture, if D is in either of the "Case 2" regions, then draw a line segment from p(A, B, D) to point C. Since the polygon is convex this line segment is entirely within the polygon (under the assumption that p(A, B, D) is within the polygon). So clearly, D is an interior point in the polygon, contradicting the assumption that it was a vertex.

    So, if p(A, B, C) is exterior to the polygon, then p(A, B, D) is also exterior to the polygon.

    --------

    But an upper limit on the number of ghost points that lie outside the polygon isn't exactly what I am trying to prove. That a maximum of 3 ghost points lie outside the polygon does not imply that n - 3 ghost points lie within it. In a regular hexagon, for example, there is only one ghost point that lies within it. The ghost points, in addition to lying outside the polygon, may lie on an edge or vertex and they may coincide with one another. So the real question I'm trying to answer is more complicated.
     
    Last edited: Feb 13, 2006
  15. Feb 13, 2006 #14
    I see a bit more of what you're getting at. I was counting the ghost points with multiplicity. The way I'm looking at it is, if you smudged each vertex slightly, how many ghost points would there be? So, the regular hexagon in my book does indeed have 6 ghost points. this allows one to prove a theorem in general without having to worry too much about special cases.

    Plus I'm thinking of the polygons as being closed, so that a ghost point lying on an edge or vertex counts as being within the polygon, although in this case clearly if we nudged one or more of the vertices in the "wrong" direction, the resulting ghost point would suddenly be outside of the polygon.

    This is a really interesting question btw.
     
  16. Feb 13, 2006 #15

    0rthodontist

    User Avatar
    Science Advisor

    Well, the original reason I was interested in this was to find lattice points. If I know that a pentagon with integer-coordinate vertices has a lattice point inside it, then I know that it can be divided into five triangles with integer-coordinate vertices, so it has area at least 5/2, which was what the Putnam question was asking. A ghost parallelogram point of three points that have integer coordinates, itself has integer coordinates, so the existence of an interior ghost point proves the existence of an interior lattice point. So in this view it does matter whether the points are distinct or not and whether they lie on an edge/corner or not.

    You could answer it the other way, and then the answer would be at least n - 3 interior ghost points, but I am interested in the way which is more complicated.


    Here is a conjecture, which I will try to prove later. For a given ghost point P, let the number of vertices that P is a ghost point of, minus 1, be the "overlap" of P. Thus, the ghost point of a regular hexagon has overlap 5. I conjecture that (a) if P is an exterior ghost point, it has overlap 0, and (b), for any convex polygon the sum of the overlaps of all ghost points of the polygon is less than or equal to 4, except for the regular hexagon for which that number is 5. I'm pretty sure of (a) and less sure of (b).
     
    Last edited: Feb 13, 2006
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Angle Paralellograms
  1. Triangle angles? (Replies: 9)

  2. Angles in 3d (Replies: 2)

  3. The angle of a curve (Replies: 4)

  4. Angle as a vector (Replies: 1)

Loading...