计算点集中极大点的算法

Question

我在算法期末考试中遇到了这个问题（现在已经完成）：

给定一个(x,y)点集P，令M(P)为给定以下P上的偏序关系时的maximal点集合：

(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) 算法？
我的直觉是它是第一个算法的修改版，但使用了一些巧妙的数据结构（可能是二叉树的修改版），不需要为每个点扫描。

是否有这样的算法适用于一般的 偏序集？
这将在给定顶点列表和常量时间查找是否存在两个给定顶点之间的有向路径的情况下找到任何有向树的叶子。

- jacobhaven

---

你的第一个算法不起作用 - 内部循环从未执行，因为M最初为空。 - Petar Ivanov

除了@PetarIvanov所写的内容之外：O(nh)解决方案就是遍历整个点集并将一个点添加到最大集合中，直到没有更多可添加的点为止。 - amit

@PeterSmith：啊，我记错了。现在已经修复了。 - jacobhaven

@amit：我不确定你所说的“将一个点添加到最大集合”是什么意思。 - jacobhaven

@QuicksilverJohny：简单的O(nh)解决方案：遍历整个点集，并选择之前未选择的最大点[可以通过标记已选择的点来完成]，将其称为p。如果没有这样的点-结束算法。否则：将p添加到最大集合中，并重复此过程。 - amit

Answer 1

那是一个非常邪恶的考试问题（除非你的讲师告诉你其中一种O(n log h)算法用于计算凸包，此时它只是“邪恶”的）。这个问题被称为2D MAXIMA，通常是计算几何学家的领域，因为它与计算凸包有着紧密的联系。我找不到关于Maxima问题的O(n log h)算法的好描述，但Timothy Chan的 O(n log h)算法可帮你了解其特点（链接在此：Timothy Chan's O(n log h) algorithm for 2D CONVEX HULL）。

- Per