0
$\begingroup$

Let $P=\{p_1,\ldots,p_n\}$ be a set of $n$ points in a 2D plane, that is $p_i\in \mathbb{R}^2$, $\forall i=1,\ldots,n$. Each point, $p_i$, is associated with a weight, $w_i \geq 0$. Imagine a axis-parallel rectangle with a fixed size that can translate in the plane. The question is how to preprocess the points so that, for all possible positions of the rectangle, it is efficient to determine the largest weight of the subset of points that can be covered by the rectangle at the same time.

Question: what are the best running time and algorithm for finding the largest weight of the subset of points? Is $O(n \log n)$ possible?

I thought this might be an easy question to answer, but I failed to find any proper reference to this question. Any thought or reference will be appreciated.

$\endgroup$
  • $\begingroup$ I'm confused by the placement of the word "Given". Are you given the points P and the rectangle dimensions together, or are you asking how to preprocess the points and later query with a given rectangle dimensions, or are the rectangle dimensions fixed in advance and the only input is the point set, or something else? $\endgroup$ – Jeffε Jun 20 '14 at 10:42
  • $\begingroup$ Hi Prof. @JɛffE, thank you for your comments. I have revised the question, and hope it will be clear now. Per your question, the points and the dimension of the rectangle (but not position) are given. I want to find a way to preprocess the points so that, for all possible positions of the rectangle, the subset of points covered by the rectangle with the largest weight can be found quickly. Thank you. $\endgroup$ – river_06 Jun 20 '14 at 14:01
  • $\begingroup$ I'm still unclear about the answer to JeffE's questions. Are we given the dimensions of the rectangle in advance (so it can be used during pre-processing), so during pre-processing, only the location of the rectangle is unknown (but the size/width/height is known)? $\endgroup$ – D.W. Jun 20 '14 at 20:37
  • $\begingroup$ @D.W., yes, you are correct. $\endgroup$ – river_06 Jun 21 '14 at 15:08
  • 1
    $\begingroup$ I encourage you to edit your question further, to make this very clear in the question (comments exist only to help you improve the question, and are not the place to put clarifications). $\endgroup$ – D.W. Jun 21 '14 at 17:43
4
$\begingroup$

Let me describe first how to solve this problem without precomputation, then I'll describe how to make use of precomputation. I'll focus on the unweighted case (each point has weight 1); all the ideas should extend to the weighted case straightforwardly.

Here is an algorithm without precomputation: Use a sweep line. Think of sweeping a vertical line from left to right. This line represents the right edge of the rectangle. The set of possible values for this sweep line will be the set of possible $x$-value of some point, so we only need to consider $O(n)$ locations of the sweep line. Imagine that it starts at the left and slowly moves rightward.

The one thing we don't know is the $y$-value of the bottom edge of the rectangle; call it $b$ (for "bottom"). However, for any specific position of the sweep line, we can build a data structure that counts the number of points in the rectangle with bottom $b$, for all $b$ (i.e., that maps from the value of $b$ to the number of points if the rectangle's bottom edge is $b$ units above the axis, and the right edge coincides with the sweep line). I suggest you use an interval tree to represent this data structure. There are $O(n)$ possible values for $b$, and thus $O(n)$ intervals in the interval tree. When we move the sweep line right, we might need to add or remove one interval from the interval tree. When the sweep line hits a new point $(x_i,y_i)$, we add a new interval to the tree for the interval $[y_i,y_i+h]$ (where $h$ is the height of the rectangle). When the sweep line hits $w$ units to the right of the point $(x_i,y_i)$, i.e., the sweep line hits $x=x_i+w$, then we delete the interval $[y_i,y_i+h]$ from the interval tree. For each location of the sweep line, we can also use the interval tree to efficiently find the rectangle that covers the most points and has its right edge coincide with the sweep line; doing that for each possible location of the sweep line gives us the optimum rectangle.

The running time of this algorithm is $O(n \lg n)$. Each insertion/deletion can be done in $O(\lg n)$ time, and we do $O(n)$ insertions and deletions, so the whole thing can be done in $O(n \lg n)$ time.

What about precomputation? Well, if we are given the width $w$ and height $h$ of the rectangle in advance, along with the set of points, then we can build all of the interval trees. Naively, it sounds like we need to store $O(n)$ interval trees, each of size $O(n)$, for a total of $O(n^2)$ space -- but one can do better. We can reduce this to $O(n \lg n)$ space in total by using persistent data structures. It is straightforward to build a persistent version of the interval tree data structure, using standard methods.

Once you've done the precomputation, given any vertical line representing the right edge of the rectangle, you can efficiently find the best rectangle that coincides with that right edge (in $O(1)$ time). (Actually, you don't need persistent data structures for that: since there are only $O(n)$ possible queries, you can just record the answer for each possible query.) I don't know if this is what you are looking for, though, as I found your question hard to understand (it was hard for me to tell what is available during precomputation and what is made available later for each query).

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.