Linearization of a two-dimensional search

Linearization of a two-dimensional search

Let the integer pair (xi, yi) be denoted by Pi. Let of a finite number of such pairs all xi be distinct and let all yi be distinct. Let the pairs be partially ordered by Pi < Pj, defined by

Pi < Pj  =  xi < xj  ∧ yi < yj

Pj is a minimal element means ¬(E i :: Pi < Pj), and it is requested to find the minimal elements. We rewrite the condition of minimality for Pj

    ¬(E i :: Pi < Pj)
=  ¬(E i : xi < xj : yi < yj)
=  (A i : xi < xj : yi ≥ yj)

Under the assumption that the pairs have been numbered in the order of increasing x, the above reduces to

(A i : i < j : yi ≥ yj)  or  (A i : i < j : yi > yj) .

In other words: scanning the y's in the order of increasing x yields a new minimal pair each time we encounter a y smaller than we have encountered so far.

Since sorting can be done in N ∙ log N steps, we have an N ∙ log N algorithm. The solution is worth noting because I could not achieve that result --to my great regret-- without destroying the symmetry between the x's and the y's. The above was triggered by a reconsideration of the longest upsequence problem.