Can two or more polygons be constructed from the same set of points using all the points once?

Question

Given a set of (X,Y) points, is it possible to create two or more polygons from the points (can be non-convex, but must use all the points exactly once), or is only one possible?

At a high level, I'm trying to figure out whether it's possible to be given a set of (X,Y) points and deterministically draw "the" polygon from them, even if the points are "unsorted". Or, whether that is ambiguous as multiple polygons are possible.

Answer 1

There is always at least one simple polygon with the given points as vertices. For instance, the polygon with least perimeter is simple, but it is hard to compute.

An easy solution is provided by Graham scan, which starts by implicitly creating a simple polygon with the given points as vertices.

If the points are all vertices of their convex hull, then there is only one simple polygon with the given points as vertices, the convex hull.

In general, there can more than one simple polygon with the given points as vertices.

The problem is called curve reconstruction and is well studied.

Answer 2

Let $ABCD$ be a square and $E$ the centre of the square. Then $$AEBCD\quad\hbox{and}\quad ABECD\quad\hbox{and}\quad ABCED\quad\hbox{and}\quad ABCDE$$ are all "proper" pentagons.