计算点集中最大点的算法

Question

我将这个作为算法决赛的最后一个问题（现已完成）：

给定一组 (x,y) 点 P，让 M(P) 为集合给定 P 上的以下部分排序的 最大 点：

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

因此：

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

给出计算具有时间复杂度的 M(P) 的算法O(nh)、O(n log n) 和 O(n log h)（其中 n = |P| 且 h=|M(P)|）

我的 O(nh) 算法：

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

我的 O(n log n)算法：

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

什么是 O(n log h) 算法？
我的直觉是，它是第一个算法的修改，但使用了一些巧妙的数据结构（可能是二叉树的修改），不需要扫描每个点。

对于一般poset是否有这样的算法？
这将在给定顶点列表的情况下找到任何有向树的叶子，并以恒定时间查找两个给定顶点之间是否存在有向路径。

Answer 1

这是一个非常非常邪恶的考试问题（除非你的老师告诉你关于凸包的 O(n log h) 算法之一，在这种情况下它只是邪恶）。

该问题称为 2D MAXIMA，通常是计算几何学家的领域，因为它与计算凸包密切相关。我找不到关于最大值问题的 O(n log h) 算法的良好描述，但是 Timothy Chan 的 2D CONVEX HULL O(n log h) 算法 应该会给您带来启发。