algorithm - 支持对一组二维点进行特定查询的数据结构

Question

我有一组二维点，我希望能够使用参数 x_min 和 n 进行以下查询:什么是 n 具有最大 y 且具有 x > x_min 的点？

在 Ruby 中改写:

class PointsThing
  def initialize(points)
    @points = points
  end

  def query(x_min, n)
    @points.select { |point| point.x > x_min }.sort_by { |point| point.y }.take(n)
  end
end

理想情况下，我的类也支持插入和删除操作。

我想不出一个数据结构可以使查询在不到 O(|@points|) 的时间内运行。有人知道吗？

Answer 1

按 x 降序对点进行排序。对于每个点，将其插入到 purely functional 中按 y 降序排列的红黑树。将所有中间树保存在一个数组中。

要查找特定的 x_min，请使用二分查找找到中间树，其中恰好插入了 x > x_min 的点。遍历这棵树找到前 n 个点。

预处理成本在时间和空间上为 O(p log p)，其中 p 是点数。查询时间为 O(log p + n)，其中 n 是查询中要返回的点数。