Erect the Fence II

Erect the Fence II

What is this problem about?

The Erect the Fence II coding problem is a variation of the Convex Hull problem, but instead of finding a polygon, you are often asked to find the Smallest Enclosing Circle. You are given a set of points and need to find the center and radius of the smallest circle that contains all the points.

Why is this asked in interviews?

Google uses this Hard difficulty geometry problem to test advanced algorithmic knowledge. Unlike the standard fence problem, this requires a randomized algorithm or a recursive approach (Welzl's Algorithm). it evaluates whether a candidate can handle complex geometric constraints and implement an algorithm with a non-obvious linear time complexity.

Algorithmic pattern used

This problem is typically solved using Welzl's Algorithm.

1. It’s a recursive algorithm: Welzl(P, R) where P is the set of points and R is the set of points on the boundary of the circle.
2. If P is empty or |R| = 3, return the circle formed by R.
3. Pick a random point p from P.
4. Find the smallest circle D for P - {p}.
5. If p is inside D, return D.
6. Otherwise, p must be on the boundary of the smallest circle. Return Welzl(P - {p}, R + {p}).

Example explanation

Suppose you have a triangle of points.

1. The smallest circle might be the circumcircle of the triangle.
2. If you add a point inside that triangle, the circle doesn't change.
3. If you add a point far away, the new smallest circle will likely have that new point on its boundary. The algorithm dynamically adjusts the circle as it processes points.

Common mistakes candidates make

• Brute Force: Trying to check every pair or triplet of points to find the circle, which is O(N^4).
• Inaccurate Math: Forgetting the formulas for the circumcircle of a triangle or the midpoint of two points.
• Not Randomizing: Welzl's algorithm is only O(N) on average if the points are processed in random order.

Interview preparation tip

Geometry problems are rare but high-stakes. If you are interviewing for a role involving graphics, maps, or physical systems, ensure you know the basics of circles, lines, and hulls.