wu :: forums
« wu :: forums - Points and Rectangles in the Plane »

Welcome, Guest. Please Login or Register.
Mar 29th, 2024, 12:37am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   cs
(Moderators: SMQ, towr, Icarus, william wu, Grimbal, Eigenray, ThudnBlunder)
   Points and Rectangles in the Plane
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Points and Rectangles in the Plane  (Read 1838 times)
Dudidu
Full Member
***





   


Posts: 227
Points and Rectangles in the Plane  
« on: Oct 22nd, 2003, 10:37am »
Quote Quote Modify Modify

Let (x1,y1,x2,y2) denote a rectangle in the plane whose lower-left corner is (x1,y1) and whose upper-right corner is (x2,y2). 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 Lips Sealed).
« Last Edit: Oct 26th, 2003, 12:36am by william wu » IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Points and Rectengles in the Plane  
« Reply #1 on: Oct 22nd, 2003, 10:55am »
Quote Quote Modify Modify

I think this can be done in O(n log(n))..
::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)
::
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Dudidu
Full Member
***





   


Posts: 227
Re: Points and Rectengles in the Plane  
« Reply #2 on: Oct 22nd, 2003, 11:02am »
Quote Quote Modify Modify

on Oct 22nd, 2003, 10:55am, towr wrote:
I think this can be done in O(n log(n))...

towr, your fast reactions to new threads is quite astonishing Shocked.
As always (almost) you're on the right direction !!!
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Points and Rectengles in the Plane  
« Reply #3 on: Oct 22nd, 2003, 11:10am »
Quote Quote Modify Modify

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 ?
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Dudidu
Full Member
***





   


Posts: 227
Re: Points and Rectengles in the Plane  
« Reply #4 on: Oct 26th, 2003, 2:50am »
Quote Quote Modify Modify

on Oct 22nd, 2003, 11:10am, 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 Tongue
IP Logged
Dudidu
Full Member
***





   


Posts: 227
Re: Points and Rectangles in the Plane  
« Reply #5 on: Nov 2nd, 2003, 8:55am »
Quote Quote Modify Modify

It seems that this problem doesn't get any attention Cry (except from towr Smiley). So, I'll try to help a little:
 
Hint 1: The algorithm should run at O(nlogn) time complexity.
Hint 2: 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).

Hope that this will help to raise the attention in this problem Grin.
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Points and Rectangles in the Plane  
« Reply #6 on: Nov 2nd, 2003, 9:22am »
Quote Quote Modify Modify

I might have allready finished this, if I didn't have two exams last week.. (but probably not, because I'm lazy Tongue)
 
::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))
::
 
[e]I wonder why I quoted what I inteded to hide[/e]
« Last Edit: Nov 5th, 2003, 11:09am by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Dudidu
Full Member
***





   


Posts: 227
Re: Points and Rectangles in the Plane  
« Reply #7 on: Nov 5th, 2003, 10:29am »
Quote Quote Modify Modify

on Nov 2nd, 2003, 9:22am, towr wrote:
I might have allready finished this, if I didn't have two exams last week.. (but probably not, because I'm lazy Tongue)

towr, stop being lazy Grin and try to solve this question.
IP Logged
James Fingas
Uberpuzzler
*****





   
Email

Gender: male
Posts: 949
Re: Points and Rectangles in the Plane  
« Reply #8 on: Nov 20th, 2003, 10:40am »
Quote Quote Modify Modify

My idea is similar, but different Grin:

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!
« Last Edit: Nov 20th, 2003, 10:41am by James Fingas » IP Logged

Doc, I'm addicted to advice! What should I do?
James Fingas
Uberpuzzler
*****





   
Email

Gender: male
Posts: 949
Re: Points and Rectangles in the Plane  
« Reply #9 on: Nov 21st, 2003, 10:50am »
Quote Quote Modify Modify

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 Wink:

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.
IP Logged

Doc, I'm addicted to advice! What should I do?
Dudidu
Full Member
***





   


Posts: 227
Re: Points and Rectangles in the Plane  
« Reply #10 on: Nov 26th, 2003, 9:33am »
Quote Quote Modify Modify

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 Roll Eyes) that you use more conventional DS to fill in this last hole.  
IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board