3
$\begingroup$



Say you have a 2D broken line you move along, but only some directions are allowed (I give you the angles relative to the usual cartesian plane):

  1. (Up-Left): $]\pi, \dfrac{\pi}{2}[$
  2. (Down-Left): $]-\pi, \dfrac{-\pi}{2}[$
  3. (Down-Right): $ ]\dfrac{-\pi}{2}, 0[$

An additional rule is that you cannot go Up-left if you just went Down-right, and vice-versa.
The goal is to prove that if you want to make a cycle out of this line, you always end up with a line that cross it-self.

Context
I'm working on unit-square graphs with a clique number of 2. The directions correspond to which corner of some squares lies inside the other. I'm trying to define some order onto the squares.
This is the last point of a proof that would allow the use of some representation of a graph, ending up with very easy to prove and useful small results.

Improve this question
$\endgroup$
10
  • $\begingroup$ "An additional rule is that you cannot go Up-right if you just went Down-left, and vice-versa. " Don't your rules say that you cannot go "up-right" at all? $\endgroup$
    – user44191
    Commented Aug 19, 2021 at 14:57
  • $\begingroup$ Indeed, i just edited it. $\endgroup$
    – Qise
    Commented Aug 19, 2021 at 15:05
  • 1
    $\begingroup$ For a bit of clarity: the rule still applies to the cycle at the initial vertex, that is, you want to exclude the case where the last edge is "down-right" and the first edge is "up-left", correct? e.g. $(0, 0), (-1, 2), (-2, 1), (0, 0)$ breaks the additional rule? $\endgroup$
    – user44191
    Commented Aug 19, 2021 at 15:13
  • $\begingroup$ You probably want to look at the winding around points close to the top-most vertex and compare to the winding close to the right-most vertex. $\endgroup$
    – Timothy Budd
    Commented Aug 19, 2021 at 15:19
  • $\begingroup$ Shouldn't Down-Right be ]- $\pi /2$,0[ instead? $\endgroup$
    – EtienneBfx
    Commented Aug 19, 2021 at 15:44

1 Answer 1

Reset to default
3
$\begingroup$

There has to be a self-intersection; the path cannot be a simple polygon.

Suppose the path were indeed simple. A vertex with maximal $y$ coordinate must connect edges that go up and then down. According to the rules, the only way this can happen is first up-left, then down-left. For a simple polygon, this implies the path is oriented counterclockwise. On the other hand a vertex with minimal $y$-coordinate must connect edges that go down-left, then up-left, implying the path is oriented clockwise: a contradiction.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Am I missing something in the rules? Why can't the lowest vertex be the last? You could reach it by a down-right step and not continue anywhere after that. $\endgroup$
    – Jukka Kohonen
    Commented Aug 19, 2021 at 19:10
  • $\begingroup$ Oh, interesting point. I guess this is a question for the OP; I had interpreted the rules as being "cyclic" so they applied to the last step followed by the first. Otherwise I think you can just make a triangle going up-left, down-left, down-right. $\endgroup$
    – Martin M. W.
    Commented Aug 19, 2021 at 19:14
  • 1
    $\begingroup$ I think that should conclude the question. I was probably not clear about it, but there is no such thing as first and last vertex. Thanks for this simple proof. $\endgroup$
    – Qise
    Commented Aug 19, 2021 at 19:31
  • 1
    $\begingroup$ Glad it's useful, and thank you for providing context and motivation in your question. Welcome to MathOverflow! $\endgroup$
    – Martin M. W.
    Commented Aug 19, 2021 at 19:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .