The direct dominance problem
Ralf Hartmut Güting, Otto Nurmi, Thomas Ottmann · 1985
Given two points a=(a1,a2,…,ad) and b=(b1,b2,…,bd) in d-dimensional space, a dominates b if a≠b and for each i=1…d holds ai≥bi. The direct dominance problem consists of computing a relation of minimal size on a given set of n points such that the transitive closure of the relation gives all the dominances in the set. We present an Ο(n log n +k) time and Ο(n) space algorithm for the problem of two-dimensional space. The algorithm is optimal within a constant factor. Further, we show that the three-dimensional problem can be solved in Ο((n+k) log2n) time and space, or alternatively in Ο((n+k) log3n) time and Ο((n+k)log n) space.