Question:
given a finite set $\mathcal{P}$ of disjoint points in the Euclidean plane and the set $\mathcal{C}$ of all simple polygons whose corners are subsets of $\mathcal{P}$,
what is the complexity of calculating the lightest subset $\mathcal{X}_{\min}\subseteq\mathcal{C}$ of unnested closed polygons that covers $\mathcal{P}$ when the weight of a polygon is defined to be equal to the length of its perimeter?
Has that problem already been investigated, resp. what kind of heuristics can used to find good approximate solutions?
Without requiring that polygons must not be nested, the solution can be calculated with Tutte's 2-factor algorithm in polynomial time, so the essential question is as to whether demanding unnestedness tips the complexity-scales to $NP$.
