I came up with following problem, Like in Any Townhouse, There are M Row houses in N lines. And a row house is a form of rectangle. In this case, Row houses are form of rectangles but not with fixed sizes, with No fixed spacing from neighbour houses AND No fixed spacing from one row to other. The Problem is given a point, We need to locate respective row house. And we want to optimize the queries ( locate a point to the respective house) as houses are laid once.
I can always check all the houses if the given point belongs to that house. But, the optimisation I am looking for is how to avoid looking at the some of the houses. For example, I can do binary search on one house (call it M1 ) and it's right house and left house, If the distance to point is reduced with left house compared to M1, then we go toward left otherwise right. But, this seems to not to work, Can you please help.
And to make it complex, What if the row house can take any arbitrary shape. Are there any similar problems in any online judge ?
PS: This question is still not answered , so any help is appreciated.
EDIT: In the earlier edit the row houses are of fixed sizes, I changed that constraint.
Having rectangles with fixed sizes and spacing makes it a very simple problem. Every rectangle starts width+Spacing from the previous one, similar for the height.
If the arbitrary shapes are convex polygons, you may check SWERC 2015 Problem J (http://swerc.eu/), where we basically asked to check if a point is inside a polygon in O(log n) time (polygon with n points).
There are linear time algorithms if the polygon is concave. See https://en.wikipedia.org/wiki/Point_in_polygon
Thanks for the reply,
But, even though checking a point if it is in rectangle is very simple, But we have to search for for all houses. For example, I can do binary search on one house (call it M1 ) and it's right house and left house, If the distance to point is reduced with left house compared to M1, then we go toward left otherwise right. But, I am not really sure about it.
Also, I updated the question rectangles but not fixed size and spacing.
Suppose, without loss of generality, that the first rectangle has its lower left corner at (0,0) and upper-right at (W, H). - The rectangle to the right has corners at (W+space, 0), (2*W+space, H), and similarly for the rectangles to the right of this one. - The rectangle above it has corners at (0, H+space), (W, 2*H+space)
To check if a point (x, y) belongs to a rectangle, we just divide x by (W+space) and y by (H+space) and we know which rectangle this point should belong to. Then we just check that rectangle.
Without fixed size and spacing, the problem is not so trivial, but it really depends on your goal. There are a number of possible approaches, depending on whether there are many queries or the positions of the rectangles. I think you would have to be a bit more specific.
To increase performance of quries you can use quadtree or more complicated Voronoi diagram.
in Q-tree it's not necessary to maintain exactly 4 children at each level. You can divide first level by x coordinate, second by y, third by x and so on. Each vertex of a tree represents some rectanlge and all houses inside this rectangle.