# Polygonal paths and polygons with prescribed set of vertices

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

• 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. – Dmitri Panov Dec 6 '19 at 10:11
• duplicate mathoverflow.net/q/226469/4312 – Fedor Petrov Dec 6 '19 at 11:43
• Fedor, since the modified question is now asking the angles not to be straight, this is not a duplicate. This version if obviously harder. – Dmitri Panov Dec 6 '19 at 12:33
• 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. – Joseph O'Rourke Dec 7 '19 at 1:14
• 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. – Gerhard Paseman Dec 7 '19 at 16:09

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

• Nice! And this is a closed cycle, a simple polygon. – Joseph O'Rourke Dec 7 '19 at 20:34
• Congratulations - nice work :) So - is the n=4 the smallest possible - what about n=3 ? – Algirdas Rugys Dec 7 '19 at 20:53
• @AlgirdasRugys: For $n=3$, there is a polygonal path (but maybe not a polygon). I added a figure to my post. – Joseph O'Rourke Dec 7 '19 at 21:17
• 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... – Dmitri Panov Dec 7 '19 at 21:26
• 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. – Algirdas Rugys Dec 7 '19 at 21:50

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

• $$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$$:

• 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. – Gerhard Paseman Dec 6 '19 at 23:17
• @GerhardPaseman: What does it mean for a path to end at a vertex, when the path must be a closed cycle? – Joseph O'Rourke Dec 7 '19 at 0:35
• 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. – Gerhard Paseman Dec 7 '19 at 0:40
• @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. – Joseph O'Rourke Dec 7 '19 at 0:43
• @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. – Joseph O'Rourke Dec 7 '19 at 1:28

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.

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