Find the shortest fence that encloses an area on a 2D grid

Question

I have a 50 x 50 2D grid. Grid cells can have one of three states:

1: "inside"
2: "empty"
3: "wall"

My initial configuration is a grid with some cells (maybe 10% of them, mostly contiguous) marked as "inside". Randomly there are some "wall" cells as well. The other cells are "empty".

I am trying to find the shortest fence I can build around the "inside" cells so that all the "inside" cells are fenced in (fences are built by changing "empty" cells to "wall" cells). If we are scoring solutions, the best solution will minimize the number of "empty" cells that need to be changed to "wall" cells.

More rigorously, in the final configuration, there is the constraint that for each "inside" cell there is no path to the edge of the grid that doesn't pass through a "wall" cell. In my case, diagonal movement is allowed.

I am guessing I can do something clever involving the distance transform, or computing the topological skeleton of the grid, but it is not immediately obvious to me. If this is a classic optimization problem, I don't know what terms to google.

Is there an O(n^2) algorithm for finding the shortest fence?

EDIT: It is not as easy as just finding the convex hull of the "inside" cells, because pre-existing "wall" cells are free. Imagine a "C"-shaped chunk of pre-existing wall, with all "inside" cells in the interior of the C. Most of the time, completing the C with "wall" cells will be cheaper than drawing a convex hull around all the "inside" cells. This is what makes this problem hard.

Answer 1

What a nice problem!

As @qwertyman has noticed, the problem is finding a minimal vertice cut between "inner" cells and the grid boundary. While it is conceivable that this special problem on a grid could have an easier solution, I don't think any of the other solutions solve the problem in all cases.

Cells on square grids can be seen as having up to four or up to eight neighbours (@tobias_k and @hidefromkgb). If we disregard the existing (free) wall cells, here's what typical fences will look like on 4- and 8-grids:

Not that in both cases, there are many more minimal fences, but these rectangular and octagonal bounding boxes are both minimal and easy to find. In addition, they are minimal fences with maximal interior area.

There are two complications: Free pre-existing wall cells, and the possiblity that multiple small fence components are cheaper than one big bounding box.

Both complications are nicely solved in a minimal vertice cut problem; pre-existing wall cells can just be deleted from the graph (and the inner cells may be merged with other, connected inner cells, leaving only one inner cell for each connected component of inner cells). Unfortunately, minimal cuts are usually considered to be removal of edges rather than vertices!

I doubt any algorithm will be easier than implementing a clean vertice cut algorithm. Here's what we're facing:

In this example, four small fences are cheaper than one big one, but that depends on the exact proportions. We could start with one big fence and try to improve it by division, like @LazyMammal does, or with fencing each connected component separately, but in either case, these situations are not trivial.

This one is problematic too:

Shall we use the large free fence segment? Shall we fence each tiny spot seperately? Shall we use three medium fences? No matter if we're starting big and divide, like @LazyMammal does, or start with individual bounding boxes and join them, these situations seem to present the same issues that general minimum cuts are solving.

If you're okay with approximations to optimal solutions, or maybe restrict yourself to instances on 50-by-50 grids and can quickly rule out these complications, maybe there is something easy and fast? I don't know.

For a connected set G of inner cells, finding a cheapest fence would work like this:

• Find a shortest "flow" path FL of empty cells from that group to the boundary.

• Find a cheapest "fence" path FE around the group using all cells not in either G or FL. Try either each cell in FL as starting point, or any cell that is both in FL and in G's fence. The cost of empty cells is 1, the cost of wall cells is 0, and the cost of inner cells not in G is 0. You'll have to temporarily cut the grid along FL to make sure FE goes around G.

(But I don't know how to fill gaps in a groups in order to connect all of its cells - in the presence of wall cells.)

So maybe the real issue is which inner cells to fence together? Connected inner cells must stay connected, alright. Also, if any minimal fences touch, join their groups. Other than that, approximate by just trying different combinations?

I don't know; I believe that the problem on large grids presents the same complications and complexity as the general minimal-cut-problems - so if you really need optimality, solve those.

Relevant: https://cstheory.stackexchange.com/questions/2877/ (thanks qwertyman), https://en.wikipedia.org/wiki/Vertex_separator with a different notion of "minimal" separators.

Answer 2

If by shortest fence you mean one which takes minimal number of "wall" cells, the fence with minimal enclosing rectangle will work.

Answer 3

What you most probably want is a 2-dimensional convex hull.

I`d recommend the so-called gift-wrapping algorithm. Its time complexity is O(n²) in the worst case. Its gist is as follows.

Without loss of generality, let`s assume that there are no 3 points in the cloud that are collinear.

1. We begin with a leftmost point, as each hull over a finite point cloud must include at least one point that is leftmost (and, considering the restrictions above, no more than two of them are possible, and they both belong to the hull).
2. Then we start to brute-force such point that all the rest are on the same of the two half-planes, into which the initial plane is divided by a line drawn from the initial point to the one searched for.
3. Now we make the found one a new initial, and then repeat [2–3] till the hull is closed.

[N.B.] bear in mind that finding a point that is a predecessor of the current initial one leads you nowhere (like this: • ⇌ •), so it should be skipped, unless there are no more points except these two.