Closest-Pair & Convex-Hull by Brute Force

Geometric Problems: Closest-Pair and Convex-Hull by Brute Force

Computational geometry algorithms process geometric objects such as points, lines, and polygons.

---

1. Closest-Pair Problem by Brute Force

Given a set $P = \{p_1, p_2, \dots, p_n\}$ of $n \ge 2$ points in the 2D Cartesian plane where $p_i = (x_i, y_i)$, find the pair of points $(p_i, p_j)$ with the smallest Euclidean distance:

$$d(p_i, p_j) = \sqrt{(x_i - x_j)^2 + (y_i - y_j)^2}$$

Algorithm

The brute-force approach computes the distance between every possible pair of distinct points and returns the minimal pair.

ClosestPoints(P):
    // Input: An array P of n points (x_i, y_i), n >= 2
    // Output: Indices of two closest points and the minimal distance
    dmin = infinity
    index1 = null
    index2 = null

    for i = 0 to n - 2 do:
        for j = i + 1 to n - 1 do:
            d = (P[i].x - P[j].x)^2 + (P[i].y - P[j].y)^2
            if d < dmin then:
                dmin = d
                index1 = i
                index2 = j

    return index1, index2, sqrt(dmin)

Optimization Tip: To avoid expensive square root operations inside the inner loop, compare the squared distances $d^2$, taking the square root only once at the very end when returning sqrt(dmin).

Complexity Analysis

• The basic operation is the squared distance calculation between points $P[i]$ and $P[j]$.
• Number of pairs examined:

$$C(n) = \sum_{i=0}^{n-2} \sum_{j=i+1}^{n-1} 1 = \frac{(n - 1)n}{2} = \Theta(n^2)$$

• Time Complexity: $\Theta(n^2)$.
• Auxiliary Space: $\Theta(1)$ (excluding input storage).

---

2. Convex-Hull Problem by Brute Force

Definition of Convex Set & Convex Hull

• A set of points $S$ in the plane is convex if for any two points $p, q \in S$, the entire line segment $\overline{pq}$ connecting them lies inside $S$.
• The convex hull of a set of $n$ points $S$ is the smallest convex polygon that encloses all points in $S$.
• The vertices of this polygon are called extreme points. Intuitively, imagine a rubber band stretched around all the pins on a board—the pins that stretch the rubber band are the extreme points.

Diagram loads as you scroll.

Geometric Property Used by Brute Force

A directed line segment connecting two points $p_i = (x_1, y_1)$ and $p_j = (x_2, y_2)$ forms part of the convex hull boundary if and only if all other $n - 2$ points lie on the same side of the line through $p_i$ and $p_j$.

The equation of a line through $(x_1, y_1)$ and $(x_2, y_2)$ is:

$$a x + b y = c$$

where:

$$a = y_2 - y_1, \quad b = x_1 - x_2, \quad c = x_1 y_2 - y_1 x_2$$

For any third point $(x, y)$, the sign of the expression:

$$S(x, y) = a x + b y - c = (y_2 - y_1)x + (x_1 - x_2)y - (x_1 y_2 - y_1 x_2)$$

indicates which half-plane $(x, y)$ falls into:

• $S(x, y) > 0$: Point lies on one side.
• $S(x, y) < 0$: Point lies on the opposite side.
• $S(x, y) = 0$: Point is collinear with the segment.

Algorithm Pseudocode

BruteForceConvexHull(P):
    // Input: A set P of n points in the plane
    // Output: Set of line segments that make up the convex hull
    HullSegments = empty set

    for i = 0 to n - 2 do:
        for j = i + 1 to n - 1 do:
            a = P[j].y - P[i].y
            b = P[i].x - P[j].x
            c = P[i].x * P[j].y - P[i].y * P[j].x

            sign_positive = 0
            sign_negative = 0

            for k = 0 to n - 1 do:
                if k != i and k != j then:
                    val = a * P[k].x + b * P[k].y - c
                    if val > 0 then sign_positive = sign_positive + 1
                    if val < 0 then sign_negative = sign_negative + 1

            // If no points fall on one of the sides, P[i]-P[j] is a hull segment
            if sign_positive == 0 or sign_negative == 0 then:
                HullSegments.add(segment(P[i], P[j]))

    return HullSegments

Complexity Analysis

• Number of candidate point pairs $(p_i, p_j)$: $\binom{n}{2} = \frac{n(n-1)}{2} = \Theta(n^2)$.
• For each pair, testing all other points $p_k$ takes $n - 2 = \Theta(n)$ operations.
• Total time complexity:

$$\Theta(n^2) \times \Theta(n) = \Theta(n^3)$$

• This cubic algorithm is extremely slow for large point sets. In Chapter 5, we will see that divide-and-conquer (Quickhull) improves this to $\Theta(n \log n)$.

---

Comparison Summary

Problem	Brute Force Strategy	Time Complexity	Improved D&C Time (Ch. 5)
Closest Pair	Test all $\approx n^2/2$ pairs	$\Theta(n^2)$	$\Theta(n \log n)$
Convex Hull	Test all pairs against all other points	$\Theta(n^3)$	$\Theta(n \log n)$ (Quickhull)

---

Exercises

Exercise 1

Given points $p_1 = (0, 0)$, $p_2 = (4, 0)$, $p_3 = (2, 3)$, and $p_4 = (2, 1)$. Test whether the line segment connecting $p_1$ and $p_2$ belongs to the convex hull using the half-plane formula.

Show solution ↓Hide solution ↑

Solution

For $p_1 = (0, 0)$ and $p_2 = (4, 0)$:

$$a = y_2 - y_1 = 0 - 0 = 0$$$$b = x_1 - x_2 = 0 - 4 = -4$$$$c = x_1 y_2 - y_1 x_2 = 0(0) - 0(4) = 0$$

Line equation test function:

$$S(x, y) = ax + by - c = 0x - 4y - 0 = -4y$$

Now test the remaining points:

• For $p_3 = (2, 3)$: $S(2, 3) = -4(3) = -12 < 0$.
• For $p_4 = (2, 1)$: $S(2, 1) = -4(1) = -4 < 0$.

Both remaining points yield strictly negative values ($S < 0$), meaning they both lie on the same side of the line. Therefore, the segment $\overline{p_1 p_2}$ is an edge of the convex hull.

Exercise 2

Can a set of $n$ points have fewer than 3 extreme points?

Show solution ↓Hide solution ↑

Solution

• If all $n$ points are collinear (lie on a single straight line), the convex hull is a line segment having only 2 extreme points (the two endpoints of the line segment).
• If all points are identical (a single distinct point), there is only 1 extreme point.
• For any non-collinear point set in 2D with $n \ge 3$, the convex hull is a polygon with at least 3 extreme points.