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$.

$\endgroup$
  • 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 Dec 6 '19 at 10:11
  • 2
    $\begingroup$ duplicate mathoverflow.net/q/226469/4312 $\endgroup$ – Fedor Petrov Dec 6 '19 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 Dec 6 '19 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 Dec 7 '19 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 Dec 7 '19 at 16:09
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

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Nice! And this is a closed cycle, a simple polygon. $\endgroup$ – Joseph O'Rourke Dec 7 '19 at 20:34
  • 2
    $\begingroup$ Congratulations - nice work :) So - is the n=4 the smallest possible - what about n=3 ? $\endgroup$ – Algirdas Rugys Dec 7 '19 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 Dec 7 '19 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 Dec 7 '19 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 Dec 7 '19 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

| cite | improve this answer | |
$\endgroup$
  • 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 Dec 6 '19 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 Dec 7 '19 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 Dec 7 '19 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 Dec 7 '19 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 Dec 7 '19 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


| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.