Linearization of a twodimensional 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) 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.


Transcriber: Kevin Hely. Last revised on 