Hi all,
Consider n lattice points in a 2D grid {(x1, y1)....(xn, yn)}. A point (x1, y1) is said to dominate another point (x2, y2) if and only if x1 > x2 and y1 > y2. 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(n2) edges, for example, if every point lies on the x = y line. But I would be happy with a graph that would INDUCE the dominator graph by transitivity.
This is not from any contest. It's just something that I'm curious about and haven't been able to make progress on.
