techInterview Discussion

A part of techInterview.org: answers to technical interview questions.

Your host: Michael Pryor

Points in a rectangle

You are given N points.
Preprocess them such that given any rectangle, we can find the  number points that lie inside the rectangle in O(log N) time.
Note that we need just the number of points not which points lie inside.
Can we do the pre-processing in O(N^2) time? What do we do in that pre-processing?
I could come up with O(N^4) pre-processing. Anything better?
PP
Monday, July 21, 2008
 
 
First solve the simple case where the points have integer coordinates between 1 and n. To prepare, compute the number of points in each rectangle with a corner at (1,1) and an opposite corner at a grid point (of which there are n^2). This can be done by computing running sums first horizontally and then vertically.

Now to answer a query for the rectangle ((a,b),(c,d)) where a < c and b < d, return count((1,1),(c,d)) - count((1,1),(a-1,d)) - count((1,1),(c,b-1)) + count((1,1),(a-1,b-1)).

The reduction to this case is straightforward.
d
Monday, July 21, 2008
 
 
d, are you assuming that the rectangles are composed of line segment parallel to the x and y axes?

Sincerely,

Gene Wirchenko
Gene Wirchenko Send private email
Tuesday, July 22, 2008
 
 
Yes. I don't know how to do arbitrary rectangles.
d
Tuesday, July 22, 2008
 
 
google "Segment Tree" or "Interval Tree"
^Shhh^
Tuesday, July 22, 2008
 
 
d:
But how to move to the real (as opposed to integer) version?
pongba Send private email
Tuesday, July 22, 2008
 
 
The way to abstract d.'s solution away from integers is, instead of using integers as grid points, use all x/y coordinates present input data. (That is, loop through the inputs remembering all x coords, and use those as your x grid points, etc.)
aph Send private email
Wednesday, July 23, 2008
 
 
In C++ish terminology...

have two multimaps with the key as X and Y co ordinates respectively, and the value as the index of the corresponding point.

Then you can use upper_bound, lower_bound and set_union, and do it in logarithmic time.

Friday, July 25, 2008
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz