12
$\begingroup$

Let's name each set of more than three points "connectable", when it is possible to connect all of the points that belong to set with n line segments (where n is number of points) in such a way that they create a n-gon that don't intersect itself. Of course, points are placed in two dimensional space.
Here are two examples of connectable sets(Sorry for bad quality of the pictures):


Next example shows points connected in improper way, the created polygon have only six sides, while the set consists of seven points(The orange point lies on the straight line segment).

This set, and the previous one are not connectable.

My question is: Can we easily determine whether given set is connectable or not?
For example the set below looks like if it wasn't connectable, but I didn't managed to prove this.
e
Thanks for all the help.

$\endgroup$
  • $\begingroup$ this seems like computer science, not math $\endgroup$ – mathworker21 Apr 30 at 18:38
3
+50
$\begingroup$

As mathworker21 noted, the question belongs to computer science, so cs.SE can be a good place to ask it. The problem can be NP-hard and I cannot propose an algorithm of better computational complexity than $O(n!)=O(\exp(n\log n))$, which checks all $(n-1)!$ cycles consisting of given points.

Concering a mathematical side of the problem, I note that it is easy to show (see the proofs below) and, probably, well-known that for any $n\ge 3$ distinct points of the plane are vertices of a non-self-intersecting polygon. So if there are no three collinear point then the polygon is an $n$-gon, and so the set of the points is completable.

Since the problem looks like a Russian olympic problem, I looked for the proofs in Russian and found two their sketches.

In the first (see Example 5 at p. 60 of [K-BK]) we take any (possibly, self-intersecting polygon) with the vertices at given points. Then we iteratively apply to it the following procedure. If the polygon has two crossing edges (say, $AC$ and $BD$) then we can replace them by edges $AB$ and $CD$ or by edges $AD$ and $BC$. It is easy to show that in one of these cases the polygon stays connected and in both cases the polygon’s perimeter decreases. So the algorithm eventually will produce a non-self-intersecting polygon.

In the second we take a leftmost point $O$ (that is, a point with a smallest $x$-coordinate) and draw from it rays to all other points. Now order the rays from below to above, and for all rays (but the topmost and the bottommost) we order the points it contains according to the distance to the origin $O$ of the ray. The closed broken line constituting the polygon starts from $O$ along the bottommost ray, then traverses the other rays acoording to the described order and returns to $O$ along the topmost ray.

References

[K-BK] Kanel’-Below A. Ya., Koval’dzhi A.K. “How non-standard problems are solved”, 4th edn., Moscow:MCNMO, 2008.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ You are right, but that is't full answer - there are sets that are connectable, but consist of collinear points. $\endgroup$ – Jakub Pawlak May 1 at 12:53

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.