837 Fundamental

Closest Pair of Points — Divide and Conquer

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Closest Pair of Points — Divide and Conquer" functional Rust example. Difficulty level: Fundamental. Key concepts covered: Functional Programming. Finding the two closest points in a set of n points naively requires O(n^2) distance comparisons. Key difference from OCaml: | Aspect | Rust | OCaml |

Tutorial

The Problem

Finding the two closest points in a set of n points naively requires O(n^2) distance comparisons. Divide-and-conquer solves this in O(n log n): split points by x-coordinate median, recursively find closest pairs in left and right halves, then check the strip of width 2*delta around the dividing line for cross-half pairs. The key insight: within the strip, each point needs to be compared against at most 7 others — a fixed constant, making the strip check O(n) total. This algorithm appears in geographic information systems (nearest neighbor queries), robotics (obstacle proximity), and computational chemistry (molecular interaction detection).

🎯 Learning Outcomes

• Split points at median x, recurse on halves, combine with strip check

• Understand the strip argument: at most 7 points fit in a delta×2*delta rectangle

• Implement the strip check: sort by y-coordinate, slide a window of 8 points

• Recognize the O(n log n) recurrence: T(n) = 2T(n/2) + O(n log n) for strip sort

• Optimize to true O(n log n) by maintaining y-sorted arrays through recursion

Code Example

#![allow(clippy::all)]
//! Placeholder

(* Closest Pair of Points O(n log n) in OCaml *)

type point = { x: float; y: float }

let dist a b =
  let dx = a.x -. b.x and dy = a.y -. b.y in
  sqrt (dx *. dx +. dy *. dy)

(* Brute force for n ≤ 3 *)
let brute_force pts =
  let n = Array.length pts in
  let best = ref infinity in
  let pair = ref (pts.(0), pts.(0)) in
  for i = 0 to n - 1 do
    for j = i + 1 to n - 1 do
      let d = dist pts.(i) pts.(j) in
      if d < !best then begin best := d; pair := (pts.(i), pts.(j)) end
    done
  done;
  (!best, !pair)

(* Strip scan: check points within delta of the dividing line, sorted by y *)
let strip_closest (strip : point list) (delta : float) : float =
  let arr = Array.of_list (List.sort (fun a b -> compare a.y b.y) strip) in
  let n = Array.length arr in
  let best = ref delta in
  for i = 0 to n - 1 do
    let j = ref (i + 1) in
    while !j < n && arr.(!j).y -. arr.(i).y < !best do
      let d = dist arr.(i) arr.(!j) in
      if d < !best then best := d;
      incr j
    done
  done;
  !best

(* Divide and conquer *)
let rec closest_pair_rec (pts_x : point array) : float =
  let n = Array.length pts_x in
  if n <= 3 then fst (brute_force pts_x)
  else begin
    let mid = n / 2 in
    let mid_x = pts_x.(mid).x in
    let left = Array.sub pts_x 0 mid in
    let right = Array.sub pts_x mid (n - mid) in
    let dl = closest_pair_rec left in
    let dr = closest_pair_rec right in
    let delta = min dl dr in
    (* Build strip: points within delta of the dividing line *)
    let strip = Array.to_list pts_x
      |> List.filter (fun p -> abs_float (p.x -. mid_x) < delta) in
    min delta (strip_closest strip delta)
  end

let closest_pair (points : point list) : float =
  let pts = Array.of_list (List.sort (fun a b -> compare a.x b.x) points) in
  closest_pair_rec pts

let () =
  let points = [
    {x=2.0;y=3.0}; {x=12.0;y=30.0}; {x=40.0;y=50.0};
    {x=5.0;y=1.0};  {x=12.0;y=10.0}; {x=3.0;y=4.0};
  ] in
  let d = closest_pair points in
  Printf.printf "Closest pair distance: %.4f\n" d;
  (* Brute force verification *)
  let arr = Array.of_list points in
  let (bf, _) = brute_force arr in
  Printf.printf "Brute force distance:  %.4f\n" bf;
  Printf.printf "Match: %b\n" (abs_float (d -. bf) < 1e-9)

Key Differences

Aspect	Rust	OCaml
Array mutation	In-place sort on `&mut [Point]`	`Array.sort` (in-place)
Splitting	Slice indexing `&mut points[..mid]`	`Array.sub` (copies)
Strip	`Vec<&Point>` — references	`Point list` or `Point array`
Base case size	`<= 3`	Same
True O(n log n)	Sort by x once, maintain y-order	`List.merge` approach
Parallel variant	`rayon::join` for halves	No built-in parallel

OCaml Approach

OCaml sorts with Array.sort and splits using Array.sub. The recursive calls work on sub-arrays. The strip check uses Array.to_list |> List.filter then List.sort by y-coordinate, followed by a sliding window. OCaml's List.fold_left computes the minimum distance in the strip. The functional style returns a new sorted-by-y array at each level (merge-sort style) for the true O(n log n) variant. Float.min combines the two recursive distances.

Full Source

#![allow(clippy::all)]
//! Placeholder

(* Closest Pair of Points O(n log n) in OCaml *)

type point = { x: float; y: float }

let dist a b =
  let dx = a.x -. b.x and dy = a.y -. b.y in
  sqrt (dx *. dx +. dy *. dy)

(* Brute force for n ≤ 3 *)
let brute_force pts =
  let n = Array.length pts in
  let best = ref infinity in
  let pair = ref (pts.(0), pts.(0)) in
  for i = 0 to n - 1 do
    for j = i + 1 to n - 1 do
      let d = dist pts.(i) pts.(j) in
      if d < !best then begin best := d; pair := (pts.(i), pts.(j)) end
    done
  done;
  (!best, !pair)

(* Strip scan: check points within delta of the dividing line, sorted by y *)
let strip_closest (strip : point list) (delta : float) : float =
  let arr = Array.of_list (List.sort (fun a b -> compare a.y b.y) strip) in
  let n = Array.length arr in
  let best = ref delta in
  for i = 0 to n - 1 do
    let j = ref (i + 1) in
    while !j < n && arr.(!j).y -. arr.(i).y < !best do
      let d = dist arr.(i) arr.(!j) in
      if d < !best then best := d;
      incr j
    done
  done;
  !best

(* Divide and conquer *)
let rec closest_pair_rec (pts_x : point array) : float =
  let n = Array.length pts_x in
  if n <= 3 then fst (brute_force pts_x)
  else begin
    let mid = n / 2 in
    let mid_x = pts_x.(mid).x in
    let left = Array.sub pts_x 0 mid in
    let right = Array.sub pts_x mid (n - mid) in
    let dl = closest_pair_rec left in
    let dr = closest_pair_rec right in
    let delta = min dl dr in
    (* Build strip: points within delta of the dividing line *)
    let strip = Array.to_list pts_x
      |> List.filter (fun p -> abs_float (p.x -. mid_x) < delta) in
    min delta (strip_closest strip delta)
  end

let closest_pair (points : point list) : float =
  let pts = Array.of_list (List.sort (fun a b -> compare a.x b.x) points) in
  closest_pair_rec pts

let () =
  let points = [
    {x=2.0;y=3.0}; {x=12.0;y=30.0}; {x=40.0;y=50.0};
    {x=5.0;y=1.0};  {x=12.0;y=10.0}; {x=3.0;y=4.0};
  ] in
  let d = closest_pair points in
  Printf.printf "Closest pair distance: %.4f\n" d;
  (* Brute force verification *)
  let arr = Array.of_list points in
  let (bf, _) = brute_force arr in
  Printf.printf "Brute force distance:  %.4f\n" bf;
  Printf.printf "Match: %b\n" (abs_float (d -. bf) < 1e-9)

Deep Comparison

OCaml vs Rust: Closest Pair Divide Conquer

Overview

See the example.rs and example.ml files for detailed implementations.

Key Differences

Aspect	OCaml	Rust
Type system	Hindley-Milner	Ownership + traits
Memory	GC	Zero-cost abstractions
Mutability	Explicit ref	mut keyword
Error handling	Option/Result	Result<T, E>

See README.md for detailed comparison.

Exercises

Implement the true O(n log n) variant that avoids re-sorting the strip by maintaining y-sorted arrays.

Extend to 3D: find the closest pair of points in 3D space using the same divide-and-conquer approach.

Use Rayon to parallelize the two recursive halves and measure speedup on 10^6 points.

Implement a KD-tree and compare its closest-pair query time against the divide-and-conquer algorithm.

Verify correctness by comparing with brute-force O(n^2) on random point sets of size up to 1000.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust