Consider a set of points randomly distributed on a $2$ dimensional coordinate plane. There should exist one solution in which each point is used once to create a shape defined by each point as a vertex. In this way, the first point is also the last point. I wish to find a process in which the area enclosed by this creates the largest possible area. I approach thusly:
- take the convex hull of the points
- Find the interior point $x$ that, when combined with two adjacent points on the convex hull (point $n$ and point $n+1$), creates a triangle of smaller area.
- insert point $x$ between point $n$ and $n+1$.
- repeat steps $2$ and $3$ until all points are included.
This seems to give me the desired solution, but I seek a proof that this is the case.
Any ideas?