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) 的解决方案(但我想我们可以拭目以待)。