Converting 2D Dominance Relation to a DAG

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

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 $\text{[math]}$ 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.