凸壳算法修正问题

Question

我最近在一次采访中被问到这个问题，但我不知道最佳方法。有人能指出我正确的方向。

预期时间复杂度为O（nlogn），所需空间复杂度为O（1）。

Answer 1

你想计算pareto-frontier或skyline。检查Maxima of a point set的算法。

由于空间复杂度应为O（1），因此必须使用就地排序算法（具有O（n log n）运行时复杂度）

Answer 2

Sort all pairs ascending by the x component. // O(n log n)
i=n, x = xn, ymax = yn, y = -infinity  // O(1)
for i = n-1 downto 0:   // O(n)
   if xi < x then x = xi, y = ymax
   if yi < y then mark pair as "defeated"
   else if yi > ymax then ymax = yi