Algorithm to Compute Maximal Points in Pointset

Question

I had this as the final question on an algorithms final (now completed):

Given a set of (x,y) points P, let M(P) be the set of maximal points given the following partial ordering on P:

(x,y) < (x',y') if and only if x < x' and y < y'.

Thus:

M({(0,0),(1,1)})={(1,1)}
M({(0,0),(0,1),(1,0)})={(0,1),(1,0)}

Give algorithms that compute M(P) with time complexity O(nh), O(n log n), and O(n log h) (where n = |P| and h=|M(P)|)

My O(nh) algorithm:

Declare M as a set of points
foreach p in P:
  addP = true
  foreach m in M:
    if(p < m):
      addP = false
      break
    if(m < p):
      M.remove(m)
  if(addP)
    M.add(p) //doesn't add if M contains p
return M

My O(n log n) algorithm:

Declare M as a set of points
Sort P in reverse lexicographic order
maxY := -inf
foreach p in P:
  if(p.y > maxY):
    M.add(p)
    maxY = p.y
return M

What is an O(n log h) algorithm?
My intuition is that it is a modification of the first algorithm, but using some clever data structure (perhaps a modification of a binary tree) that doesn't need to be scanned through for each point.

Is there such an algorithm for a general poset?
This would find the leaves of any directed tree given a list of vertices and constant time lookup of whether there is a directed path between two given vertices.

Answer 1

That's a really really evil exam question (unless your instructor told you about one of the O(n log h) algorithms for convex hull, in which case it's merely evil).

The problem is called 2D MAXIMA and is the typically the domain of computational geometers because of its close relationship to computing convex hulls. I can't find a good description of a O(n log h) algorithm for the maxima problem, but Timothy Chan's O(n log h) algorithm for 2D CONVEX HULL should give you the flavor.