Function get_potential_left_corner_tiles 

fn get_potential_left_corner_tiles(
    sorted_tiles: impl Iterator<Item = [u32; 2]>,
) -> (Vec<[u32; 2]>, Vec<[u32; 2]>)

This function filters sorted_tiles into two lists, one containing all tiles that could be the top left corner of the largest rectangle (assuming the largest rectangle has a top left corner), and the second containing all tiles that could be the top right corner.

It assumes sorted_tiles is sorted in ascending “y” values, or, to get the top right and bottom right corners, that sorted_tiles is sorted in descending “y” order.

It works (for the top left corners, for illustration) by only returning tiles (from the set of all tiles, “T”) within the region:

R = { (x, y) ∈ ℝ² : ∀ (tx, ty) ∈ T, tx ≤ x ⇒ ty ≥ y }

Tiles outside of this region cannot possibly be a corner of the largest rectangle. Assume, for proof by contradiction, that the top left corner of the largest rectangle is in the complement of the set “R”:

R’ = { (x, y) ∈ ℝ² : ¬ (∀ (tx, ty) ∈ T, tx ≤ x ⇒ ty ≥ y) } = { (x, y) ∈ ℝ² : ∃ (tx, ty) ∈ T, tx ≤ x ∧ ty < y }

That is, for the corner (x, y), there exists another tile (tx, ty) that is to the left and above the corner tile, which means the tile isn’t the corner of the largest possible rectangle, completing the proof by contradiction.

The top_tiles and bottom_tiles are the corner points of this region R, built up by scanning through tiles in either left to right or right to left order.

With just this selection of candidate edge points, the number of points that have to be compared is already reduced compared to a naive quadratic pairing of all original points. But exploiting the relationships we just proved above, we can further reduce the comparisons to O(n log n) by repeatedly picking the mid-point of top_tiles, finding which corresponding point in bottom_tiles forms the best rectangle, and then recursively checking just two of the four combinations of the sublists remaining on either side of the pivots. This post goes more into the theory.