wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Points and Rectangles in the Plane
        
(Message started by: Dudidu on Oct 22^nd, 2003, 10:37am)

Title: Points and Rectangles in the Plane
Post by Dudidu on Oct 22^nd, 2003, 10:37am

Let (x₁,y₁,x₂,y₂) denote a rectangle in the plane whose lower-left corner is (x₁,y₁) and whose upper-right corner is (x₂,y₂). Devise an efficient algorithm which, when given n rectangles represented as above and n points in the plane, decides which point is inside the largest number of rectangles.

Notice: basic knowledge of data structures is needed (I can't review those DS's since it will help to solve the problem :-X).

Title: Re: Points and Rectengles in the Plane
Post by towr on Oct 22^nd, 2003, 10:55am

I think this can be done in O(n log(n))..
::[hide]a plane-sweep (or sweep-line) algorithm should do nicely I think..
So we need to sort the rectangles on their x1-coordinate, and the points on their x-coordinate (both n log(n)), and set up eventlines (for the points, and the start and end of the rectangles)
The real problem is figuring out what to do on the sweepline, since that's where the tricky stuff is dealt with (and it's been a while since I dealt with it)..
Afterwards you know in how many rectangles each point lies and you can easily find the maximum in O(n)
[/hide]::

Title: Re: Points and Rectengles in the Plane
Post by Dudidu on Oct 22^nd, 2003, 11:02am

on 10/22/03 at 10:55:31, towr wrote:

I think this can be done in O(n log(n))...

towr, your fast reactions to new threads is quite astonishing :o.
As always (almost) you're on the right direction !!!

Title: Re: Points and Rectengles in the Plane
Post by towr on Oct 22^nd, 2003, 11:10am

One question, though not very important. If there are two rectangles right next to each other, and a point exactly on the border, is it in 0, 1 or 2 rectangles ?

Title: Re: Points and Rectengles in the Plane
Post by Dudidu on Oct 26^th, 2003, 2:50am

on 10/22/03 at 11:10:09, towr wrote:

One question, though not very important. If there are two rectangles right next to each other, and a point exactly on the border, is it in 0, 1 or 2 rectangles ?

The 4-tuple points represent an open rectangle.
Sorry that I wasn't clear :P

Title: Re: Points and Rectangles in the Plane
Post by Dudidu on Nov 2^nd, 2003, 8:55am

It seems that this problem doesn't get any attention :'( (except from towr :)). So, I'll try to help a little:

Hint 1: [hide]The algorithm should run at O(nlogn) time complexity.[/hide]
Hint 2: [hide]towr made quite important progress (although not complete) and reached the core of the problem (i.e. "The real problem is figuring out what to do on the sweepline") - so I suggest that anyone who has ideas about what should be done on the sweepline, suggest them, so others could help him to put these ideas into the "data-structural context" (i.e. to reach the desired complexity).[/hide]

Hope that this will help to raise the attention in this problem ;D.

Title: Re: Points and Rectangles in the Plane
Post by towr on Nov 2^nd, 2003, 9:22am

I might have allready finished this, if I didn't have two exams last week.. (but probably not, because I'm lazy :P)

::[hide]This still won't complete it, but basicly 'on the sweepline' you keep a binary-tree which keeps score how many rectangles are 'active' between adjacent nodes.
It mostly a matter of administration for removing and adding squares. for a point you can simply look up between which points of the sweepline it lies, and there you find the record for how many rectangles it lies in.
To keep it efficient you have to keep the tree balanced so that lookup takes only log(n) time, which makes it n log(n) to do it for every point (and sorting also took n log(n))[/hide]::

[e]I wonder why I quoted what I inteded to hide[/e]

Title: Re: Points and Rectangles in the Plane
Post by Dudidu on Nov 5^th, 2003, 10:29am

on 11/02/03 at 09:22:41, towr wrote:

I might have allready finished this, if I didn't have two exams last week.. (but probably not, because I'm lazy :P)

towr, stop being lazy ;D and try to solve this question.

Title: Re: Points and Rectangles in the Plane
Post by James Fingas on Nov 20^th, 2003, 10:40am

My idea is similar, but different ;D:
[hide]
I will define the problem recursively. A "tableau" is a collection of up to n rectangles and n points located inside a finite bounding rectangle.

It is possible to divide a tableau up into two smaller tableaus. When this is done, you split any rectangles on the dividing line into two pieces. Each tableau will have up to 2n non-degenerate horizontal lines (sides of a rectangle) in it, and up to 2n non-degenerate vertical lines in it. The split is made along one of these lines. A line is "degenerate" if it lies along the bounding rectangle. The line that is chosen for this split will be the median non-degenerate vertical line if the non-degenerate lines are mostly vertical, and otherwise will be the median non-degenerate horizontal line.

Stop recursively dividing the tableaus into sub-tableaus when the tableau either has no point (in it), or when it contains no non-degenerate divisions (this is called a "degenerate tableau").

I think this takes only time O(n log n), but the analysis is somewhat complicated![/hide]

Title: Re: Points and Rectangles in the Plane
Post by James Fingas on Nov 21^st, 2003, 10:50am

towr,

Thinking more about this problem, I think my solution might be O(n^2) or worse, so if you don't mind me taking the liberty, I'll finish your solution ;):
[hide]
We will be sweeping a vertical line across the plane, while maintaining a binary tree that states what horizontal lines cross that vertical line. Where the vertical line coincides with rectangle sides, we add and/or remove horizontal lines. When the vertical line hits a point, we can count up the number of rectangles it's in in O(log n) time.

Pre-processing: for every vertical rectangle side (two per rectangle), record the following information:

Key: x location
Add/Subtract: Add if the side is an x1, subtract if it's an x2 side
Positive Horizontal Line: y1
Negative Horizontal Line: y2

Now sort these sides by their key, taking O(n log n) time.
Sort the points by their x location, taking O(n log n) time.

Each internal node will contain one key, a boolean indicating whether it's a positive or a negative line, and a single integer giving the net number of positive horizontal lines in its left branch. The binary tree starts as empty.

Now sweep horizontally through the list of sides and points simultaneously. When you get to a side, do the following (assumes add/subtract is "add"):

1) For the positive line, search for its location in the tree, adding +1 to the value stored at each node where you go left. Add the new horizontal line when you get to a leaf. Rebalance the tree if necessary.

2) For the negative line, search for its location in the tree, adding -1 to the value stored at each node where you go left. Add the new horizontal line when you get to a leaf. Rebalance the tree if necessary.

If add/subtract were "subtract", you would subtract +/-1 instead of adding it, and remove the line.

When you hit a point, search for its location in the tree, keeping a running total of how many horizontal lines are above it. This can be done based on the values stored in the internal nodes (too lazy to figure out exactly how).

This solution is complete, except that it does not deal with the problems you can encounter when two horizontal lines are coincident. That should be easy to deal with, however.
[/hide]

Title: Re: Points and Rectangles in the Plane
Post by Dudidu on Nov 26^th, 2003, 9:33am

James hi,
Sorry that it took me so long to reply.
I've looked at your answer and the general idea is correct ! thumbs up !
However, I do not fully understand the tree DS that you suggested (more specifically, I do not understand how (and if) you can get the number of rectangles that a point lie in from the values that you hold in the tree).
I suggest (for the sake of simplicity ::)) that you use more conventional DS to fill in this last hole.