Hi all,

Consider n lattice points in a 2D grid

Unable to parse markup [type=CF_TEX]

. A point (x₁, y₁) is said to dominate another point (x₂, y₂) if and only if x₁ > x₂ and

Unable to parse markup [type=CF_TEX]

. Obviously this dominance relation defines a DAG: G has an edge

Unable to parse markup [type=CF_TEX]

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

Unable to parse markup [type=CF_TEX]

edges. But I would be happy with a graph that would INDUCE the dominator graph by transitivity.

So, in the example above, instead of

Unable to parse markup [type=CF_TEX]

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.