Problem Description

The "Erect the Fence II" problem asks you to find the minimum perimeter fence that encloses all the given trees (represented as 2D points) in a garden. The fence must pass through the outermost trees, and all trees located on the boundary of the fence must be included. The input is a list of points, trees, where each point is a pair [x, y] representing the coordinates of a tree.

• You must return all the trees that are on the perimeter of the fence, in any order.
• If multiple valid solutions exist, you may return any of them.
• Do not reuse points; each tree appears only once in the output.
• The answer must include all trees that are on the boundary (even if colinear).

The challenge is to compute the convex hull of the given points, including all points that lie on the hull's edges, not just the vertices.

Thought Process

To solve this problem, one might first think of checking every possible way to connect the trees and see which configuration encloses all of them with the smallest perimeter. However, this brute-force approach is computationally infeasible for large inputs.

Instead, we can use concepts from computational geometry. The convex hull of a set of points is the smallest convex polygon that contains all the points. Imagine stretching a rubber band around the outer trees: the shape it forms is the convex hull.

There are several algorithms to compute the convex hull, such as Graham scan and Jarvis March (Gift Wrapping). For this problem, we need to ensure all points on the boundary (including colinear ones) are included. The standard convex hull algorithms can be adapted to handle this requirement.

Solution Approach

We will use the Monotone Chain Algorithm (a variant of Graham scan) to find the convex hull. Here's how we proceed:

1. Sort the points: First, sort all the points by their x-coordinate (and by y-coordinate if x's are equal). This helps in constructing the hull in an orderly fashion.
2. Build the lower hull: Iterate through the sorted points and use the cross product to determine if the current point creates a left turn or a right turn. If it creates a right turn (or is colinear), remove the last point from the hull. Continue until you can't remove any more points.
3. Build the upper hull: Repeat the process in reverse (from the largest to smallest x) to build the upper part of the hull.
4. Include colinear points on the boundary: If the cross product is zero (meaning points are colinear), include those points as well, as required by the problem.
5. Combine the hulls: Concatenate the lower and upper hulls, removing duplicate points.
6. Return the result: The resulting list contains all the trees on the perimeter of the fence.

The cross product is used to determine the orientation of three points: a positive value means a left turn, negative means a right turn, and zero means colinear.

Example Walkthrough

Suppose the input is trees = [[1,1], [2,2], [2,0], [2,4], [3,3], [4,2]].

1. Sort points: [[1,1], [2,0], [2,2], [2,4], [3,3], [4,2]]
2. Build lower hull:
   • Add [1,1], [2,0]
   • Add [2,2] (left turn)
   • Add [2,4] (left turn)
   • Add [3,3] (right turn, so remove [2,4] and try again)
   • Continue until all points are processed
3. Build upper hull in reverse order:
   • Start from [4,2], [3,3], ...
   • Use the same cross product logic to determine turns
4. Combine hulls and remove duplicates:
   • Final result: [[1,1], [2,0], [4,2], [3,3], [2,4]]

All boundary trees, including those on the edges, are included in the result.

Time and Space Complexity

• Brute-force approach: Checking all possible polygons would have exponential time complexity, which is impractical for large datasets.
• Optimized (Monotone Chain): Sorting the points takes O(n log n). Building the hulls is O(n), as each point is added and removed at most once. So, total time complexity is O(n log n).
• Space Complexity: We store the sorted list and the hulls, so the space complexity is O(n).

Summary

The "Erect the Fence II" problem is a classic computational geometry challenge that can be efficiently solved using the convex hull algorithm. By using the Monotone Chain method and carefully handling colinear points, we can ensure all boundary trees are included. The approach is efficient, elegant, and leverages geometric insights for optimal performance.

Code Implementation

from typing import List

class Solution:
    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:
        def cross(o, a, b):
            return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

        trees = sorted(map(tuple, trees))
        if len(trees) <= 1:
            return [list(p) for p in trees]

        lower = []
        for p in trees:
            while len(lower) >= 2 and cross(lower[-2], lower[-1], p) < 0:
                lower.pop()
            lower.append(p)

        upper = []
        for p in reversed(trees):
            while len(upper) >= 2 and cross(upper[-2], upper[-1], p) < 0:
                upper.pop()
            upper.append(p)

        # Remove the last point of each half because it's repeated at the beginning of the other half
        result = set(lower + upper)
        return [list(p) for p in result]
      

class Solution {
public:
    vector<vector<int>> outerTrees(vector<vector<int>>& trees) {
        sort(trees.begin(), trees.end());
        vector<vector<int>> lower, upper;
        for (auto& p : trees) {
            while (lower.size() >= 2 && cross(lower[lower.size()-2], lower[lower.size()-1], p) < 0)
                lower.pop_back();
            lower.push_back(p);
        }
        for (int i = trees.size() - 1; i >= 0; --i) {
            while (upper.size() >= 2 && cross(upper[upper.size()-2], upper[upper.size()-1], trees[i]) < 0)
                upper.pop_back();
            upper.push_back(trees[i]);
        }
        set<vector<int>> s(lower.begin(), lower.end());
        s.insert(upper.begin(), upper.end());
        return vector<vector<int>>(s.begin(), s.end());
    }
private:
    int cross(const vector<int>& o, const vector<int>& a, const vector<int>& b) {
        return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]);
    }
};
      

class Solution {
    public int[][] outerTrees(int[][] trees) {
        Arrays.sort(trees, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
        List<int[]> lower = new ArrayList<>();
        for (int[] p : trees) {
            while (lower.size() >= 2 && cross(lower.get(lower.size()-2), lower.get(lower.size()-1), p) < 0)
                lower.remove(lower.size()-1);
            lower.add(p);
        }
        List<int[]> upper = new ArrayList<>();
        for (int i = trees.length - 1; i >= 0; --i) {
            while (upper.size() >= 2 && cross(upper.get(upper.size()-2), upper.get(upper.size()-1), trees[i]) < 0)
                upper.remove(upper.size()-1);
            upper.add(trees[i]);
        }
        Set<List<Integer>> set = new HashSet<>();
        for (int[] p : lower) set.add(Arrays.asList(p[0], p[1]));
        for (int[] p : upper) set.add(Arrays.asList(p[0], p[1]));
        int[][] res = new int[set.size()][2];
        int idx = 0;
        for (List<Integer> p : set) {
            res[idx][0] = p.get(0);
            res[idx][1] = p.get(1);
            idx++;
        }
        return res;
    }
    private int cross(int[] o, int[] a, int[] b) {
        return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]);
    }
}
      

/**
 * @param {number[][]} trees
 * @return {number[][]}
 */
var outerTrees = function(trees) {
    trees.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
    function cross(o, a, b) {
        return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]);
    }
    const lower = [];
    for (const p of trees) {
        while (lower.length >= 2 && cross(lower[lower.length-2], lower[lower.length-1], p) < 0)
            lower.pop();
        lower.push(p);
    }
    const upper = [];
    for (let i = trees.length - 1; i >= 0; --i) {
        const p = trees[i];
        while (upper.length >= 2 && cross(upper[upper.length-2], upper[upper.length-1], p) < 0)
            upper.pop();
        upper.push(p);
    }
    const set = new Set();
    for (const p of lower) set.add(p.toString());
    for (const p of upper) set.add(p.toString());
    return Array.from(set).map(s => s.split(',').map(Number));
};