title: Algorithm to Compute Maximal Points in Pointset
body: <p>I had this as the final question on an algorithms final (now completed):</p>
  
  <p>Given a set of (x,y) points <strong>P</strong>, let <strong>M(P)</strong> be the set of <strong><a href="http://en.wikipedia.org/wiki/Maximal_element" rel="nofollow">maximal</a> points</strong> given the following partial ordering on P:</p>
  
  <pre><code>(x,y) &lt; (x',y') if and only if x &lt; x' and y &lt; y'.
  </code></pre>
  
  <p>Thus:</p>
  
  <pre><code>M({(0,0),(1,1)})={(1,1)}
  M({(0,0),(0,1),(1,0)})={(0,1),(1,0)}
  </code></pre>
  
  <p>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)|)</p>
  
  <p>My O(nh) algorithm:</p>
  
  <pre><code>Declare M as a set of points
  foreach p in P:
    addP = true
    foreach m in M:
      if(p &lt; m):
        addP = false
        break
      if(m &lt; p):
        M.remove(m)
    if(addP)
      M.add(p) //doesn't add if M contains p
  return M
  </code></pre>
  
  <p>My O(n log n) algorithm:</p>
  
  <pre><code>Declare M as a set of points
  Sort P in reverse lexicographic order
  maxY := -inf
  foreach p in P:
    if(p.y &gt; maxY):
      M.add(p)
      maxY = p.y
  return M
  </code></pre>
  
  <p><strong>What is an  O(n log h) algorithm?</strong><br>
  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.</p>
  
  <p><strong>Is there such an algorithm for a general <a href="http://en.wikipedia.org/wiki/Partially_ordered_set" rel="nofollow">poset</a>?</strong><br>
  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.</p>