5

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

给定一组 (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？
这将在给定顶点列表和恒定时间查找两个给定顶点之间是否存在有向路径的情况下找到任何有向树的叶子。

4

1 回答 1

6

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

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

于 2011-12-14T15:56:31.687 回答