<p>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). </p>

<p><img src="https://i.sstatic.net/1FHcl.jpg" alt="Illustration of how a single cut removes a hole"></p>

<blockquote>
  <p>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 ? </p>
</blockquote>

<p>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. </p>

<p>Is this a known problem ? </p>

CC BY-SA 3.0
2014-04-11T01:55:04.320Z
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?
Jeffε
CC BY-SA 3.0
2014-04-11T02:44:21.217Z
IIIUC, we can assume the holes are triangles without loss of generality, right?
Kaveh
CC BY-SA 3.0
2014-04-11T03:41:21.193Z
@Kaveh that sounds about right.
Suresh Venkat
CC BY-SA 3.0
2014-04-11T03:43:14.247Z
@JɛﬀE 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.
Suresh Venkat
CC BY-SA 3.0
2014-04-11T10:48:45.870Z
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.
babou
CC BY-SA 3.0
2014-07-16T09:53:39.973Z
The MST gives you a 2 approximation. I would suggest asking Joe Mitchell - he wrote several papers on remotely related problems (Zoo keeper problem, and TSP of disks, if my memory serves me right).
Sariel Har-Peled
<ds.algorithms><cg.comp-geom><polygon>
Minimum length cuts needed to remove holes in a polygon
Suresh Venkat
# Minimum length cuts needed to remove holes in a polygon

(Asked by: username_0 on 2014-04-11)

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](https://i.sstatic.net/1FHcl.jpg)

> 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 ?

**Tags:** ds.algorithms, cg.comp-geom, polygon

> **Comments:**
> **username_1**: 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?  
> **username_2**: IIIUC, we can assume the holes are triangles without loss of generality, right?  
> **username_0**: @username_2 that sounds about right.  
> **username_0**: @JɛﬀE 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.  
> **username_3**: 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.  
> **username_4**: The MST gives you a 2 approximation. I would suggest asking Joe Mitchell - he wrote several papers on remotely related problems (Zoo keeper problem, and TSP of disks, if my memory serves me right).  

---

## 0 answers

