Hi all,

Consider n lattice points in a 2D grid {(x₁, y₁)....(x_n, y_n)}. A point (x₁, y₁) is said to dominate another point (x₂, y₂) if and only if x₁ > x₂ and y₁ > y₂. Obviously this dominance relation defines a DAG: G has an edge if point u dominates point v. Let us call this the dominance graph.

My question is this, is it possible to efficiently (say in time O(nlog(n))) compute the dominance graph?

Obviously, the dominance graph could have O(n²) edges. For example, if every point lies on the x = y line, then each point would dominate all points below it, giving us ⁿC₂ edges. But I would be happy with a graph that would INDUCE the dominator graph by transitivity.

So, in the example above, instead of ⁿC₂ edges, it is sufficient to keep n - 1 edges.

This is not from any contest. It's just something that I'm curious about and haven't been able to make progress on. I don't even know if this graph is going to be sparse enough to be explicitly computed.