LeetCode Solutions Blog

Erect the Fence II

Number: 2074

Difficulty: Hard

Paid? Yes

Companies: Google

Problem Description

Given a set of 2D points representing trees in a garden, determine the smallest possible circle (with center and radius) that encloses all the trees. The circle must be as tight as possible so that its circumference (rope length) is minimized.

Key Insights

The problem is an instance of computing the Minimum Enclosing Circle (or Smallest Enclosing Circle).
A well-known approach is based on Welzl’s algorithm, which works in expected linear time after randomization.
The optimal circle can be defined by 1, 2, or 3 points on its boundary.
Handling collinear points is important: when three points are collinear, the result comes from the two farthest apart.

Space and Time Complexity

Time Complexity: Expected O(n); worst-case O(n^2)
Space Complexity: O(n)

Solution

We use a randomized algorithm (Welzl’s algorithm) to compute the minimum enclosing circle. The algorithm works as follows:

Randomize the order of the input points.
Iterate through each point and check if it is inside the current circle. If it is not, update the circle using that point as a boundary.
When a point is found outside the circle, consider all previous points. Recalculate the circle using pairs (or triplets) of points that force the circle to pass through these boundary points.
For 2 boundary points, the circle’s center is the midpoint and the radius is half of the distance.
For 3 boundary points, use the circumcenter formula, and handle degenerate (collinear) cases where necessary.

This approach gradually and probabilistically builds up the minimal circle that encloses all trees.

Code Solutions

import random
import math

# Compute Euclidean distance between two points
def distance(a, b):
    return math.hypot(a[0] - b[0], a[1] - b[1])

# Create a circle from one point (radius 0)
def circle_from_one_point(p):
    return (p, 0)

# Create a circle from two points: center is midpoint and radius is half the distance
def circle_from_two_points(p, q):
    cx = (p[0] + q[0]) / 2.0
    cy = (p[1] + q[1]) / 2.0
    r = distance(p, q) / 2.0
    return ((cx, cy), r)

# Create a circle from three points using the circumcenter formula
def circle_from_three_points(p, q, r):
    ax, ay = p
    bx, by = q
    cx, cy = r
    d = 2 * (ax*(by - cy) + bx*(cy - ay) + cx*(ay - by))
    if abs(d) < 1e-8:
        # Collinear points: choose the circle from the two farthest points
        candidates = [circle_from_two_points(p, q), circle_from_two_points(p, r), circle_from_two_points(q, r)]
        return min(candidates, key=lambda cir: cir[1])
    ux = ((ax*ax + ay*ay)*(by - cy) + (bx*bx + by*by)*(cy - ay) + (cx*cx + cy*cy)*(ay - by)) / d
    uy = ((ax*ax + ay*ay)*(cx - bx) + (bx*bx + by*by)*(ax - cx) + (cx*cx + cy*cy)*(bx - ax)) / d
    center = (ux, uy)
    radius = distance(center, p)
    return (center, radius)

# Check if point p is inside the circle (with a tiny tolerance)
def is_inside(circle, p):
    center, r = circle
    return distance(center, p) <= r + 1e-8

# Welzl's algorithm (iterative version) to compute the minimum enclosing circle
def min_enclosing_circle(points):
    shuffled = points[:]
    random.shuffle(shuffled)
    circle = None
    for i, p in enumerate(shuffled):
        if circle is None or not is_inside(circle, p):
            circle = (p, 0)
            for j in range(i):
                q = shuffled[j]
                if not is_inside(circle, q):
                    circle = circle_from_two_points(p, q)
                    for k in range(j):
                        r = shuffled[k]
                        if not is_inside(circle, r):
                            circle = circle_from_three_points(p, q, r)
    return circle

# Main function that takes the list of trees and returns [x, y, radius]
def find_minimal_circle(trees):
    center, r = min_enclosing_circle(trees)
    return [center[0], center[1], r]