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

OK I solved the problem, but I haven't computed the asymptotic complexity.

I did it through Dynamic Progamming, where I defined the problem recursively, and also adding a culling criteria for a good speedup.

Here is the recursive problem statement:

Find the smallest fencing set in a such that there is no path from a startArea to a border.
The recursive problem is provided with:

• a grid containing natural, pre-existing walls
• a startArea
• a Border definition
• a pre-existing set of fences that were placed and cannot be removed
• a maximum number of fences N

Return the following:

• If a fencing is found, return a List of the fences
• If no fences are required, return an empty list
• If the fence size must exceed N walls, return <invalid> (e.g. null)

The solution to this statement was done using this observation:

Any fencing should contain at least one wall on the optimal path from the start area to the border (Otherwise, that path would be valid and be used to escape)

Therefore, a way to solve the recursive problem statement is as follows:

Initialize the recursive algorithm by providing:

• The initial world
• The startArea,
• The border definition (e.g. cell must be on the frontier of the grid)
• An empty list of initial fences
• A maximum number of fences set to Positive_Infinity (no constraint)

Then recurse as follows:

• Generate the shortest path from startArea to the border without passing through existing fences
• If no path leads to the exit, return the pre-defined fences
  • Rationale: the path is blocked, the existing fencing is sufficient, no need to add any
• If the pre-defined fences have at least Nelements, return <invalid>
  • Rationale: the pre-defined fences are insufficient, so at least N+1fences would be required. Since a solution with N fences is known to exist, no need to investigate further
• Initialize bestLength as the input maximum number of fences N as
• Initialize bestPath as ìnvalid
• Iterate over each location along the path (excluding cells that are in the startArea, which I assume cannot be walled off)
  • generate a solution to the recursive problem as follows:
    • the input grid containing natural, pre-existing walls
    • the input startArea
    • the input Border definition
    • the pre-existing set of fences plus the current location
    • the maximum number of fences bestLength
  • If the solution is <invalid>, continue iterating
  • If the solution exists
    • Store it as bestPath
    • Update bestLength its length
  • If the solution length is N+1 return it
• Return bestPath

---

Basically, we're walling the best paths as we find them. As we wall on, the path changes and we wall that.

The best bit IMO is the culling mechanism, similar to a beta-pruning.

Dirty complexity analysis (The grid is NxN):

• The path has a length N, we're iterating over its length.
  • Each recursive iteration creates a path of length N (normally it's longer, but I'll ignore that). Thanks to culling I'll make this a complexity of log(N) only
    • At each step we're performing BFS so N.log(N)

Total Complexity: N².log(N)²` (maybe? I don't know what I'm doing)

---

Here's a Java version of it:

MinimalFenceSolver.java (main class)

The problem is constructed in the main, and solved is static methods.

public class MinimalFenceSolver {

    public static final Predicate<Location> borderDetector = loc -> ((GridWorld.GridLocation)loc).isBorder();

    public static void main(String[] argc){
        GridWorld world = new GridWorld(10, 10, 0);

        // Find best fence
        List<Location> startArea = new ArrayList<>();
        startArea.add(world.at(5, 4));
        findBestFence(world, startArea);
    }

    private static List<Location> findBestFence(GridWorld world, List<Location> startArea) {
         List<Location> bestFence = findBestFenceRec(world, startArea, new ArrayList<>(), Integer.MAX_VALUE);
        return bestFence;
    }

    private static List<Location> findBestFenceRec(GridWorld world, List<Location> startArea, List<Location> fencePrefix, int bestLengthYet) {
        List<Location> bestFence = null;
        int bestLength = bestLengthYet;

        // Iterate
        World fencedWorld = world.withWall(fencePrefix);
        Path shortestPath = EscapePathfinder.begin(fencedWorld).setStart(startArea).setEnd(borderDetector).solve();
        if(!shortestPath.exists()){
            return fencePrefix;
        }

        if(fencePrefix.size() >= bestLength){
            return null; // Culling
        }

        for (Location loc : shortestPath.fullPath()) {
            if(!fencePrefix.contains(loc) && !startArea.contains(loc)){
                List<Location> newfence = new ArrayList<>(fencePrefix);
                newfence.add(loc);
                List<Location> bestChild = findBestFenceRec(world, startArea, newfence, bestLength);
                if(bestChild != null){
                    if(bestFence == null || bestChild.size() < bestLength) {
                        bestFence = bestChild;
                        bestLength = bestChild.size();
                    }
                }
            }
        }

        return bestFence; // null if no fence found 
    }
}

World.java interface for a world definition

public interface World {

     Location at(int i, int j);

     /**
      * Removes walled Locations in the input, return the result
      * @param neighbours (untouched)
      * @return a List of Locations, none of which has any wall in it
      */
    List<Location> noWalls(List<Location> neighbours);

}

Location.java interface

public interface Location {
     CellType getType();
     List<Location> neighbours();
}

CellType.java enum

public enum CellType {
    WALL, EMPTY
}

GridWorld.java an implementation of a World that lives on a Grid

Contains its own Location implementation. Has the ability to be temporarily decorated with additional fences using the GridWorldWithWall subclass.

public class GridWorld implements World{

    private final GridLocation[][] world;
    final int nx;
    final int ny;

    public GridWorld(int nx, int ny, long seed){
        this.nx = nx;
        this.ny = ny;
        Random rand = new Random(seed);
        world = new GridLocation[nx][ny];
        for(int i=0; i<nx; i++){
            for(int j=0; j<ny; j++){
                CellType locationType = rand.nextBoolean() ? CellType.EMPTY: CellType.WALL;
                world[i][j] = new GridLocation(locationType, i, j);
            }
        }
    }

    public GridLocation at(int i, int j){
        return world[(i+nx) % nx][(j+ny) % ny];
    }

    public String toString(){
        StringBuilder builder = new StringBuilder();
        for(int i=0; i<nx; i++){
            for(int j=0; j<ny; j++){
                builder.append(world[i][j].type == CellType.WALL ? "#" : ".");
            }
            builder.append("\n");
        }
        return builder.toString();
    }

    private static final int[][] offsets = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public class GridLocation implements Location{

        private final CellType type;
        private final int i;
        private final int j;

        public GridLocation(CellType type, int i, int j) {
            super();
            this.type = type;
            this.i = i;
            this.j = j;
        }

        @Override
        public CellType getType() {
            return type;
        }

        @Override
        public List<Location> neighbours() {
            List<Location> result = new ArrayList<>();
            for(int[] offset: offsets){
                result.add(GridWorld.this.at(i + offset[0], j + offset[1]));
            }
            return result;
        }

        public boolean isBorder(){
            return i==0 || j==0 || i==nx-1 || j==ny-1;
        }

        public String toString(){
            return (type == CellType.WALL ? "#" : ".") + "(" + i + ", " + j + ")";
        }

        public boolean equals(Object obj){
            if(!(obj instanceof GridLocation)){
                return false;
            } else {
                GridLocation other = (GridLocation) obj;
                return other.i == this.i && other.j == this.j;
            }
        }
    }

    @Override
    public List<Location> noWalls(List<Location> neighbours) {
        return neighbours.stream().filter(cell -> cell.getType()!=CellType.WALL).collect(Collectors.toList());
    }

    public World withWall(List<Location> walls) {
        return new GridWorldWithWall(walls);
    }

    private class GridWorldWithWall implements World {

        public List<Location> walls;

        public GridWorldWithWall(List<Location> walls) {
            this.walls = walls;
        }

        @Override
        public Location at(int i, int j) {
            return new LocationWithWalls(GridWorld.this.at(i, j));
        }

        @Override
        public List<Location> noWalls(List<Location> neighbours) {
            List<Location> noWalls = GridWorld.this.noWalls(neighbours);
            noWalls.removeAll(walls);
            return noWalls;
        }

        private class LocationWithWalls implements Location{
            private final GridLocation location;
            public LocationWithWalls(GridLocation location) {
                this.location = location;
            }

            @Override
            public CellType getType() {
                if(GridWorldWithWall.this.walls.contains(location)) {
                    return CellType.WALL;
                }
                return location.getType();
            }

            @Override
            public List<Location> neighbours() {
                List<Location> neighbours = location.neighbours();
                neighbours().removeAll(walls);
                return neighbours;
            }

        }
    }
}

Pathfinder.java (Interface)

This is an overkill fluent interface in case you want to try other solvers, if you manage to make a good heuristic for the border, a-Star can be used here

public interface Pathfinder {

    public static interface PathStartSetter {

        PathEndSetter setStart(Iterator<? extends Location> startSupplier, Predicate<Location> startTester);

        default PathEndSetter setStart(final Location start){
            return setStart(
                new Iterator<Location>() {

                    boolean provided = false;

                    @Override
                    public boolean hasNext() {
                        return !provided;
                    }

                    @Override
                    public Location next() {
                        if(provided){
                            return null;
                        } else {
                            provided = true;
                            return start;
                        }
                    }
                },
                loc -> loc.equals(start)
            );
        }

        default PathEndSetter setStart(final List<Location> start){
            return setStart(start.iterator(),
                loc -> start.contains(loc)
            );
        }

    }

    public static interface PathEndSetter{

        public PathSolver setEnd(Predicate<Location> endTester);


        default PathSolver setEnd(final Location end){
            return setEnd(loc -> loc.equals(end));
        }

        default PathSolver setEnd(final List<Location> end){
            return setEnd(loc -> end.contains(loc));
        }
    }

    public static interface PathSolver{
        public Path solve();
    }

    public static interface Path{
        List<Location> fullPath();
        Location pathAt(int step);
        public boolean exists();
    }

    public static class NoPath implements Path {

        @Override
        public List<Location> fullPath() {
            return null;
        }

        @Override
        public Location pathAt(int step) {
            return null;
        }

        @Override
        public boolean exists() {
            return false;
        }

    }
}

Dijkstra.java (The Typical BFS solver)

Feel free to skip reading it, it's vanilla dijkstra, but it does implement my convoluted Pathfinder interface

public class Dijkstra implements Pathfinder{

    public static DijkstraStartSetter begin(World world) {
        return new DijkstraStartSetter(world);
    }

    public static class DijkstraStartSetter implements PathStartSetter {
        private final World world;
        public DijkstraStartSetter(World world) {
            this.world = world;
        }

        public DijkstraEndSetter setStart(Iterator<? extends Location> startSupplier, Predicate<Location> startTester) {
            return new DijkstraEndSetter(world, startSupplier, startTester);
        }
    }

    public static class DijkstraEndSetter implements PathEndSetter{

        private final World world;
        private final Iterator<? extends Location> startSupplier;
        private final Predicate<Location> startTester;

        public DijkstraEndSetter(World world, Iterator<? extends Location> startSupplier, Predicate<Location> startTester) {
            this.world = world;
            this.startSupplier = startSupplier;
            this.startTester = startTester;
        }

        public DijkstraSolver setEnd(Location end){
            return new DijkstraSolver(world, startSupplier, startTester, end);
        }

        public DijkstraSolver setEnd(Predicate<Location> endTester){
            return new DijkstraSolver(world, startSupplier, startTester, null);
        }
    }

    public static class DijkstraSolver implements PathSolver{

        private final World world;
        private final Iterator<? extends Location> startSupplier;
        private final Predicate<Location> startTester;
        private final Location end;

        public DijkstraSolver(World world, Iterator<? extends Location> startSupplier, Predicate<Location> startTester, Location end) {
            this.world = world;
            this.startSupplier = startSupplier;
            this.startTester = startTester;
            this.end = end;
        }

        public Path solve(){
            Queue<Location> open = new LinkedList<>();
            List<Location> closed = new ArrayList<>();
            Map<Location, Location> parents = new HashMap<>();
            while (startSupplier.hasNext()) {
                open.add(startSupplier.next());
            }
            while(!open.isEmpty()){
                Location current = open.remove();
                closed.add(current);
                List<Location> neighbours = world.noWalls(current.neighbours());
                for (Location n : neighbours) {
                    if(open.contains(n) || closed.contains(n)) {
                        continue;
                    }
                    open.add(n);
                    parents.put(n, current);
                    if(n == end){
                        return makePath(parents);
                    }
                }
            }
            return new NoPath();
        }

        private Path makePath(Map<Location, Location> parents) {
            StandardPathBuilder path = StandardPath.begin();
            Location current = end;
            while(!startTester.test(current)){
                path.add(current);
                current = parents.get(current);
            }
            path.add(current);
            return path.buildReverse();
        }
    }

}

---

Sorry for the amazingly long post and over-engineered solution! I just loved the Question so much I got carried away.

Answer 2

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 3

This can be solved as a graph simplification problem:

1. create a graph of the grid (no diagonals)
2. remove (delete) Inside nodes
3. collapse (merge) Wall nodes
4. describe a path around the edge of the graph
5. iterate along the path
   • check if nearby path nodes share an empty graph neighbour (nearby = path nodes[n .. n+k] )
   • check if new path distance <= existing path distance (count edges)
   • check if Inside node would be stranded by shortcut (don't allow)
   • adjust path if conditions are met
   • remove (delete) graph nodes that are no longer needed
6. stop when path cannot be shrunk anymore

Worst case you have to traverse all the vertex nodes in the graph a few times for each edge. So it looks like O(V * E) or in other words O(N^2).

Answer 4

For me it's still a convex hull variant. you have to include in your convex hull all cells that are neighbors to inside cell and that are not an inside cell + include cells that are at the [beginning] and [end] of a wall (contiguous wall). Then important part is to exclude neighbor cells if those cells are inside a wall. To check if cell is inside a wall shaped C for example(I) you can compute ax+b line from p1--p2, then using a kind of point partitioning check clockwise/counterclockwise and then further wall points with your neighbor point to exclude it from search. In example below points neighbors to I are going to be excluded. Thus algorithm will find p1->p2 connection p1-p2 as straight forward.

...[.p1]
. I 
. I 
...[.p2]

In the example below T points are neighbor points

               TTT
...[.p1]       TIT
. I            TTT
. I 
...[.p2]

after convex hull algo you will get:

               [T3]
...[.p1]        I[T2]
. I            [T1] 
. I 
...[.p2]

that means a path p2[T1][T2][T3]p1 and lines between between those points gives you minimal wrap. As you can see each wall have to store as well a value if any I neighbor point is INSIDE a wall shape (like C), those walls have to be included in convex hull, but the ones that have no internal neighbors can be used only if distance to next point is smaller using zero cost existing wall.. Well its a bit complicated for quick explanation but i suppose you can get something from that..

EDIT: On that computed convex you will have to run also min flow to tune up cases like:

...........[.]
.
.
. 
.
.         
.
.         I  I
.
.
.
.
.
. 
...........[.]

where one of I is inside but min fence is around both I's without p1 and p2 involved. In algo p1 and p2 will be selected, then for all walls that have internal I you have to compute dist(p1,externalI)+dist(p2,externalI) with dist(internalI,eternalI)and choose the smaller one..externalI is the one connected to p1 and p2 (could be one ore two external points..)

Answer 5

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.

Answer 6

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