Highest weight search point in the region
My problem:
We have a set of points N
in two-dimensional space, each of which has a weight. For any area of the rectangle R
, how to effectively return the point with the greatest weight inside R
?
Note that all query areas R
have the same shape, that is, the same length and width. Point and rectangle coordinates are floating point numbers.
My initial idea is to use R
-tree to store points. For the area, R
select all points in R
and then find the point with max. weight. Time complexity O(logN + V)
, where V
is the number of points in R
. Can we do better?
I tried to find a solution but still failed. Any suggestion?
Thank,
source to share
This sounds like a problem with the maximum range request in 2D. You have some very good algorithms here .
The easiest way would be to just use a 2D segment tree.
Basically, each node of your segment tree will store 2d areas instead of 1d spacing. This way, each node will have 4 children, reducing to a square tree that you can work with just like a classic segment tree. This is detailed here .
This will be O(log n)
per request, where n
is the total number of points. It also allows you to do a lot more things like updating point weights, updating area weights, etc.
source to share
How do I add an extra attribute for each tree node that contains the maximum weight of all points contained in any of its children.
This will update easily as you add points. There will be a little more work to maintain when you remove the point that will change the maximum. You will need to traverse the tree backward and update the maximum value for all parent nodes.
With this attribute, if you want to get the point of maximum weight, then when you query for a query-scoped tree, you only check the child of the maximum weight node as you move through the tree. Please note, you can have more than one point with the same maximum weight, so you can check more than one child node.
Only checking the child nodes with the maximum weight attribute will improve the throughput of your query at the expense of more memory and slower tree creation / modification times.
source to share
Look at the so-called range trees, which in your case you would like to be implemented in two dimensions. It would be a two-layer "tree of trees" where you first split a set of points based on x-coordinate, and then for each set of x-points at one of the nodes in the resulting tree, you build a tree by y-coordinate for those points at that node in the source tree. You can see how to adapt a two range tree to return the number of points in the query rectangle in O ((log n) ^ 2), regardless of the number of points. Likewise, instead of storing the number of points for the sub-elements in the range tree, you can store the maximum objective value of the points within that rectangle. This will give you O (n log n) storage and build times, and O ((log n) ^ 2) query times.regardless of the number of points in the query rectangle.
Adapting so called "fractional cascading" for a range tree "find all points in a query rectangle" can even get query times up to O (log n), but I'm not sure since you are taking the maximum value of the points in a query rectangle.
source to share
Hint:
Each point has a "zone of influence", which is the locus of positions (upper left corner) of the rectangle, so this point dominates. A plurality of zones of influence determines the subdivision of the plane. Each split edge occurs at the abscissa [ordinate] of the given point or its abscissa [ordinate] minus the width [height] of the query area.
If you map coordinate values to their rank (by sorting on both axes), you can think of this section as a digital representation of the dimension 4N²
. To precompress this image, initialize it with minus infinity, and for each point, you fill your zone of influence with your weight, taking the maximum. If the query window size is R²
average pixels, the cost of rendering the image NR²
.
The query is executed by looking up the row and column of the corresponding pixel and returning the pixel value. This requires two dichotomous searches in time Lg(N)
.
This approach is only realistic at moderate values N
(say before 1000
). A better understanding of this problem can be gained by examining the geometry of the tiling display.
source to share
You can try a weighted voronoi chart where positive weight is subtracted from Euclidean distance. High weight sites have large cells with nearby low weight sites. Then sort the cells by the number of sites and calculate the minimum bounding box for each cell. Align it with the rectangular search box.
source to share