sumit93's blog

points and rectangle
By sumit93, 10 years ago, In English

I have n two dimensional points and some rectangle.For each rectangle I have to answer how much point is inside of that rectangle? How can I answer this with complexity log(n)?

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Find count point in rectangle is a standart problem.

It problem can solved with segment tree.

In each vertex we must save all vertex of need segment in sort array.

Then, we find need segment for one coordinate and make request in segment tree in need segment.

More information on Russian language: http://e-maxx.ru/algo/segment_tree#15

→ Reply
»
10 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

The simplest solution came to my head is the solution using persistent segment tree. Imagine that for each X coordinate you have a segment tree in which tree[Y] is the number of points(x, y) that have y == Y and x <= X. Then if you want to know how much points are inside of a rectangle with upper left vertex (X1, Y1) and lower right vertex (X2, Y2), the answer will be the sum from Y1 to Y2 in a segment tree with X == X2 minus the sum from Y1 to Y2 in a segment tree with X == X1 — 1. This solution takes O(Nlog(MaxY)) time and O(N * MaxY) memory where N is the number of points plus the number of rectangles. But if you use persistent segment tree, you'll decrease the memory usage down to O(Nlog(MaxY))

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Ox, Oy and rectangle edges are parallel, you can use 2D fenwick tree.

See this.

→ Reply