Data structure to support a particular query on a set of 2D points

Question

I have a set of 2D points, and I want to be able to make the following query with arguments x_min and n: what are the n points with largest y which have x > x_min?

To rephrase in 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

Ideally, my class would also support an insert and delete operation.

I can't think of a data structure for this which would enable the query to run in less than O(|@points|) time. Does anyone know one?

Answer 1

Sort the points by x descending. For each point in order, insert it into a purely functional red-black tree ordered by y descending. Keep all of the intermediate trees in an array.

To look up a particular x_min, use binary search to find the intermediate tree where exactly the points with x > x_min have been inserted. Traverse this tree to find the first n points.

The preprocessing cost is O(p log p) in time and space, where p is the number of points. The query time is O(log p + n), where n is the number of points to be returned in the query.