Given a simple polygon, i.e. a set of n vertices with a given order, at most n line segments are required to connect the points in the correct order and close the chain, thereby completing the polygon. Exactly n line segments are required if the points are in general position (i.e. no three consecutive points are colinear).
The points can be connected and closed by fewer than n arcs (we will consider a straight line segment to be an arc). Since any three points are either colinear or cocircular, we can connect any three consecutive points with an arc, then do the next three, and so on. In this way we can connect and close the points with about n/2 arcs. Fewer arcs may be required if the points are not in general position.
What if we make the stipulation that these arcs may not cross each other? How hard is this minimization problem then? Is this a candidate for dynamic programming? Or is it even NP-hard?
We consider the problem under the restriction that only the following are allowed:
We note that if none of the arcs we want will ever intersect each other, then ceiling(n/2) arcs will suffice and the solution can be found trivially. In particular, this is the case when the original polygon is convex.
We note that, in a way, arcs are restricted in terms of how many other arcs they can interfere with. This suggests that dynamic programming may be capable of solving the problem. On the other hand, the neighbourhood of interference is not restricted, i.e. one arc can interfere with an arc on the other side of the polygonal chain, so perhaps the problem is hard.
We have now determined that this problem is NP-complete. The NP-hardness proof is done via a reduction from Planar 3SAT. We are currently working on the write-up.