7
$\begingroup$

Let $A$ be a finite set of points in the plane. How can we determine if there is a simple open polygonal path (i.e. without intersections), whose vertices are exactly $A$, with no straight angles between adjacent sides? Since in mathoverflow.net/q/226469/4312 question is only about cycles, the stronger question also remains. Namely - how to determine if there exists a polygon with non-intersecting sides and without straight angles, whose vertices are exacly $A$ ?

Particular interesting case is when $A$ is a set of points $(x;y)$ with $0\leq x+y \leq 2n$ , where $x,y$ are nonnegative integers. Hypothesis : no for path for $n=1$ and $n=2$.

Improve this question
$\endgroup$
13
  • 1
    $\begingroup$ Such an $n$-gon exists always provided the points don't lie on one line. Suppose that there are $3$ points $p, q, r\in A$ that don't lie on one line. Take a generic point $O$ inside the triangle $pqr$, such that no line containing two points from $A$ passes through $O$. Once you do this, you can enumerate all the points of $A$ in the anti-clockwise order with respect to $O$, $A=p_1,\ldots, p_n$. Then you join each $p_i$ with $p_{i+1}$ by a segment (and $p_n$ with $p_1$). This will clearly give you the desired $n$-gon. $\endgroup$
    – Dmitri Panov
    Commented Dec 6, 2019 at 10:11
  • 2
    $\begingroup$ duplicate mathoverflow.net/q/226469/4312 $\endgroup$
    – Fedor Petrov
    Commented Dec 6, 2019 at 11:43
  • 3
    $\begingroup$ Fedor, since the modified question is now asking the angles not to be straight, this is not a duplicate. This version if obviously harder. $\endgroup$
    – Dmitri Panov
    Commented Dec 6, 2019 at 12:33
  • 2
    $\begingroup$ Is "a broken line" what would normally be called a (closed) simple polygon (an đť‘›-gon as per @Dmitri), or is it instead an open, simple polygonal path? The term "broken line" does not have a standard definition in the (English) literature. $\endgroup$
    – Joseph O'Rourke
    Commented Dec 7, 2019 at 1:14
  • 2
    $\begingroup$ For n=1, Joseph has a diagram of impossibility. Likely a more complicated one exists for n=2. However, there is a path for n=3 and thus for all higher n. Break into the union of a central point and 3 of (n=3/2) size triangles with overlap. One has a path from the center filling the triangles in a cyclic order, and can end on an external vertex. Gerhard "Seeing Spots Before My Eyes" Paseman, 2019.12.07. $\endgroup$
    – Gerhard Paseman
    Commented Dec 7, 2019 at 16:09

3 Answers 3

Reset to default
5
$\begingroup$

The following polygon is a counterexample to the hypothesis for $n=4$. Namely we consider the set of integer points $(x,y)|0\le x+y\le 8$. The picture is on a square-lined paper, where the size of one square is $\frac{1}{2}\times \frac{1}{2}$

The picture was constructed in collaboration with Svetlana Ermakova.

So my guess that it will be possible to do the same thing for all $n\ge 4$

enter image description here

Improve this answer
$\endgroup$
5
  • 2
    $\begingroup$ Nice! And this is a closed cycle, a simple polygon. $\endgroup$
    – Joseph O'Rourke
    Commented Dec 7, 2019 at 20:34
  • 2
    $\begingroup$ Congratulations - nice work :) So - is the n=4 the smallest possible - what about n=3 ? $\endgroup$
    – Algirdas Rugys
    Commented Dec 7, 2019 at 20:53
  • 1
    $\begingroup$ @AlgirdasRugys: For $n=3$, there is a polygonal path (but maybe not a polygon). I added a figure to my post. $\endgroup$
    – Joseph O'Rourke
    Commented Dec 7, 2019 at 21:17
  • 2
    $\begingroup$ Me too, I don't see for a while whether such a polygon exists for $n=3$. I would give more than 50% chance that it doesn't. But I have not thought yet how to prove it, just made about 100 unsuccessful pictures... $\endgroup$
    – Dmitri Panov
    Commented Dec 7, 2019 at 21:26
  • $\begingroup$ Nice path, Joseph. So it seems, here are questions for $0 \leq x+y \leq 4$ for path and $0 \leq x+y \leq 6$ for a polygon. $\endgroup$
    – Algirdas Rugys
    Commented Dec 7, 2019 at 21:50
4
$\begingroup$

Not an answer, just an illustration for $6$ points, $0 \le x+y \le 2$.

      Poly3

  • $A,B,C$: Point $3$ cannot connect to $1$ or $6$, so it must connect to $2,5$ or $4,5$ or $2,4$.
  • $B$: Point $6$ is now isolated by $34$ from $1$ and $2$.
  • $C$: Point $1$ is now isolated by $34$ from $5$ and $6$.
  • $D$: $1$ is trapped.
  • $E$: $2$ is trapped.

(Later.) Here is a simple polygonal path through the $28$ lattice points $0 \le x+y \le 6$:
      Path6

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ You can reduce this to whether a path ends at vertex 1 or not. When it doesn't, symmetry gives two cases that are easily checked. A slow divide and conquer algorithm can handle the general problem in a similar way. Gerhard "Knows No Fast Algorithm Yet" Paseman, 2019.12.06. $\endgroup$
    – Gerhard Paseman
    Commented Dec 6, 2019 at 23:17
  • $\begingroup$ @GerhardPaseman: What does it mean for a path to end at a vertex, when the path must be a closed cycle? $\endgroup$
    – Joseph O'Rourke
    Commented Dec 7, 2019 at 0:35
  • $\begingroup$ I interpret a broken line as a broken line segment, which has the (topological) shape of a path, not of a cycle. Gerhard "Who Sometimes Does Not Return" Paseman, 2019.12.06. $\endgroup$
    – Gerhard Paseman
    Commented Dec 7, 2019 at 0:40
  • $\begingroup$ @GerhardPaseman: Ah, and I was assuming a "broken line" is a polygon. Your interpretation may be the correct one. Clearly there is confusion over this issue. $\endgroup$
    – Joseph O'Rourke
    Commented Dec 7, 2019 at 0:43
  • $\begingroup$ @GerhardPaseman: The OP clarified---Your interpretation is what he intended, mine was incorrect. Still my example shows there is no simple polygonal path through those $6$ points, turning at each. $\endgroup$
    – Joseph O'Rourke
    Commented Dec 7, 2019 at 1:28
2
$\begingroup$

This paper addresses similar (but I don't think identical) questions. In any case, a key search phrase is covering path.

Dumitrescu, Adrian, Dániel Gerbner, Balázs Keszegh, and Csaba D. Tóth. "Covering paths for planar point sets." Discrete & Computational Geometry 51, no. 2 (2014): 462-484. Journal link.

DGKT

What appears to be unique is the OP's insistence that there is a turn at every vertex--no collinearities. Of course, if the points are in general position, there is automatically a turn at every vertex.
         
          Fig.2

Improve this answer
$\endgroup$

You must log in to answer this question.

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