Suppose I'm given a connected polygon in the plane with holes. I can "remove" a hole by drawing a straight line from the boundary of a hole to another boundary (either of another hole, or the boundary separating the polygon from the exterior).

Illustration of how a single cut removes a hole

Let's say the "cost" of a cut is its length. What is the minimum cost set of cuts needed to remove all holes in a polygon ?

At first I thought this would be easy: write down the distances between each pair of holes and each hole and the polygon boundary, and compute an MST. But it's not obvious to me that this is correct.

Is this a known problem ?

  • 3
    $\begingroup$ Suppose your polygon is a large square with several tiny point-like holes near its center. Do you want the solution to resemble the Euclidwan MST of the points/holes, or their Euclidean Steiner tree? $\endgroup$ – Jeffε Apr 11 '14 at 1:55
  • $\begingroup$ IIIUC, we can assume the holes are triangles without loss of generality, right? $\endgroup$ – Kaveh Apr 11 '14 at 2:44
  • $\begingroup$ @Kaveh that sounds about right. $\endgroup$ – Suresh Venkat Apr 11 '14 at 3:41
  • 1
    $\begingroup$ @JɛffE Ah good point. so if I only allow cuts between vertices then I think you're arguing that looks like MST (+ one nearest neighbor) otherwise I could end up solving Euclidean Steiner tree. That sounds almost like an answer to me. $\endgroup$ – Suresh Venkat Apr 11 '14 at 3:43
  • $\begingroup$ It seems that an issue is whether you are allowed to cut "half-lines" that connect on a common vertex, or if you are restricted to full lines going from one boundary to another, including one just created by a previous line. It seems that the latter case does not have the same kind of constructive symmetry between, say, 3 polygons to be connected, that the former may have, like the Steiner tree problem. Or may-be it is a matter of continuity vs combinatorics. And I do not think that the latter case would be MST either. $\endgroup$ – babou Apr 11 '14 at 10:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.