algorithm - O(n) 中的主要点集

Question

所以，如果给定两个点 A(x1,y1) 和 B(x2,y2)，如果 x1 <= x2 和 y1<= y2，那么我们说 B 支配 A。现在，给定很多点，我希望找出所有非支配点。简单的方法是将每个点与其他点进行比较并获得所有非支配点。但它是 O(n^2)。所以我尝试了分而治之，非常简单，我可以在 O(nlogn) 中找到它。我们的教授说，它仍然可以在 O(n) 内完成。我觉得这真的不可能。我不是要你为我解决这个问题，而是想知道是否有任何“明显”的方式可以确定在任何条件下都不能在 O(n) 中完成？但是，如果确实有可能，请不要回答，也许可以提供一些线索。

Answer 1

如果这些点已经按其中一个坐标（例如 x 坐标）排序，则可以在 O(n) 中完成，如下所示：

• 从最大的 x 坐标处理点。
  • 当您浏览它们时，请跟踪最大的 y 坐标。
  • 如果当前点的 y 坐标小于迄今为止最大的 y 坐标，则它被另一个点支配。否则，它不是被支配的，所以将它添加到输出中。

如果这些点尚未排序，我认为没有 O(n) 解决方案（但我想我们可以拭目以待）。