Closest Pair of Points - Algorithm Tutorial | Repovive

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/algorithms/closest-pair

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/algorithms/closest-pair

Repovive

Closest Pair of Points - Algorithm Tutorial | Repovive | Repovive

The Strip Case

Why is the strip check efficient?

Consider points in the strip sorted by y-coordinate. For each point $p$ , we only need to check points $q$ where $|q.y - p.y| < d$ .

Key lemma: In a $d \times 2d$ rectangle centered on the dividing line, there can be at most 8 points (at most 4 on each side).

This is because each side has minimum pairwise distance $d$ , so in a $d \times d$ square, at most 4 points can fit (one in each corner).

Implication: For each point in the strip, we check at most 7 subsequent points (by y-coordinate). So the strip check is $O(n)$ , not $O(n^2)$ .

function strip_closest(strip, d):
    sort strip by y-coordinate
    min_d = d
    for i from 0 to len(strip)-1:
        j = i + 1
        while j < len(strip) and (strip[j].y - strip[i].y)^2 < min_d:
            min_d = min(min_d, dist_sq(strip[i], strip[j]))
            j++
    return min_d

Complete Algorithm

function closest_pair(points):
    if len(points) <= 3:
        return brute_force(points)

    // Sort by x-coordinate
    sort points by x

    mid = len(points) / 2
    mid_x = points[mid].x

    // Divide
    left = points[0:mid]
    right = points[mid:]

    // Conquer
    d_left = closest_pair(left)
    d_right = closest_pair(right)
    d = min(d_left, d_right)

    // Build strip
    strip = []
    for p in points:
        if (p.x - mid_x)^2 < d:
            strip.append(p)

    // Combine
    d_strip = strip_closest(strip, d)

    return min(d, d_strip)

Base case: For 2 or 3 points, brute force is efficient.

Sorting: Initial sort is $O(n \log n)$ . Maintain sorted order during recursion or re-sort the strip (still $O(n \log n)$ overall).

Complexity Analysis

Time Complexity:

Let $T(n)$ be the time for $n$ points.

$T(n) = 2T(n/2) + O(n)$

The $O(n)$ term comes from:

Building the strip: $O(n)$
Sorting strip by y: $O(n \log n)$ but can be $O(n)$ with merge
Checking strip: $O(n)$ (at most 7 comparisons per point)

By the Master Theorem: $T(n) = O(n \log n)$

Space Complexity: $O(n)$

Storing points
Recursion depth: $O(\log n)$
Strip array: $O(n)$

Comparison with naive:

Algorithm	Time	Space
Brute Force	$O(n^2)$	$O(1)$
Divide & Conquer	$O(n \log n)$

For $n = 50000$ : brute force needs $\approx 1.25 \times 10^9$ operations, D&C needs $\approx 800000$ .

Closest Pair of Points Algorithm Tutorial

Introduction

Practice this Algorithm

Divide and Conquer Approach

The Strip Case

Complete Algorithm

Complexity Analysis