Erect the Fence II - Solution & Explanation

Problem Overview: You are given coordinates of trees on a 2D plane and must build a circular fence that encloses all of them. The goal is to compute the smallest possible circle that contains every point, also known as the minimum enclosing circle.

Approach 1: Brute Force Circle from Pairs and Triplets (O(n^4) time, O(1) space)

The smallest enclosing circle is uniquely determined by either two boundary points (forming the diameter) or three boundary points (forming a circumcircle). A brute force strategy enumerates every pair and triplet of points, constructs the corresponding circle, and checks whether all points lie inside it. For each candidate circle you iterate through the entire point set to verify containment. This produces a worst-case time complexity of O(n^4) for triplet enumeration and validation, with constant auxiliary space. It works conceptually but is far too slow for large inputs.

Approach 2: Reduced Enumeration with Geometric Observations (O(n^3) time, O(1) space)

You can slightly reduce the brute force work by generating circles only from pairs and triplets and validating them immediately. For every pair of points, construct the circle whose diameter is the segment between them. For every triple, compute the circumcircle using standard geometry formulas. After constructing each candidate circle, iterate through all points and ensure their distance from the center is within the radius. This reduces redundant work but still runs in O(n^3) time. It’s mostly useful for understanding the geometric properties behind the optimal solution.

Approach 3: Randomized Welzl’s Algorithm (Expected O(n) time, O(n) space)

The optimal solution uses Welzl’s algorithm, a randomized incremental technique for computing the minimum enclosing circle. Shuffle the points first, then process them one by one. Maintain the current minimal circle. If the next point already lies inside it, continue. If it lies outside, the point must be on the boundary of the final circle. Recompute the circle using that point plus up to two previously processed boundary points. This recursion maintains a small boundary set of size at most three. Because the boundary size is constant and each point is processed once on average, the expected running time is O(n) with O(n) space for recursion and storage.

This algorithm relies heavily on geometric primitives: computing distances, constructing a circle from two points (diameter midpoint), and computing the circumcircle of three points using coordinate geometry. The problem combines concepts from array iteration with computational geometry and numerical reasoning from math.

Recommended for interviews: Randomized Welzl’s algorithm. Interviewers expect you to recognize the minimum enclosing circle pattern and apply the randomized incremental approach. Explaining the brute force pair/triple observation first shows geometric intuition, but implementing Welzl’s algorithm demonstrates strong algorithmic skill and understanding of computational geometry.