How to sweep like a Sir

Revision en36, by DanAlex, 2015-09-17 22:17:36

Cutting to the chase

Clearly you don't need a PhD in Computing to sweep in the yard , but one might be useful in order to know linear and radial sweep algorithms. So , what's all about ? It's just what it sounds it is , sweeping linear ( up to down , for example ) or radial ( making a 360 degrees loop ).

How this can help ? Well...

Linear sweep

Suppose you a set of objects in an Euclidean plane. We need to extract information about some objects. The method of linear sweeping takes a line and moves it on a fixed direction. Usually the line taken would be vertical and the direction would be left to right or up to down.

Quite abstract for the moment , huh ? Let's go to a more specific example.

Rectangle union area

This example is well known. You have a set of rectangles with edges parallel to the OX and OY axes. What is their union area.

Well , first of all , let's take a particular case in order to achieve a different perspective. Let's suppose the lower edges are fixed on the OX axis. This would lead us to the following case :

Now let's take a look at the property we established. The property fixes the lower edge. So the only edge we are interested in is the upper edge. The other two will be united by the point projections of the ends of the edge. For example D and C will be projected in B and A. Furthermore , these edges are useless in our problem so we will take into acount only the upper edges.

Now as we established that the sweep can go. We will "move" an imaginary line from left to right. As we meet a left corner of the segment we should take it into account for the moment. When we reach it's end it should not be considered any more. On a space between two sweep lines we take all the active segments and memorise the bigest Y. The area added would be maxY * length between sweep lines.

The only remaining question is how we move the imaginary line ? Sorting , of course.

Now let's summarise. We divide each segment in two types of queries : in ( a segment is active ) and out ( a segment becomes unactive ). Sort the queries increasingly by X coordinate and for each two consecutive sweep lines take the maximum Y out of the active sweep lines. We can easily do that with a priority queue. Therefore , the complexity would be O(N log N).

To be sure we understood all , let's look again at the example. The queries will be : in(D) , in(F) , out(C) , out(G) , in(J) , out(K). On interval DF' we have one active segment , therefore maxY = 2. On interval F'C we have two active segments , maxY = 3 from FG segment. On interval CG , maxY = 3 and finally on interval JK , maxY = 5. Total area is 3*2 + 1*3 + 4*3 + 1*5 = 26. Easy.

Now as we sorted that out, let's return to our original problem. Picture , yey: ( from TopCoder tutorial )

Now how to solve stuff like that if we have different Y coordinates for down edges. Well , we'll keep the principles stated above but use a different data structure : segment trees. First normalize all Y coordinates ( keep a vector with sorted Ys and work with the order in that sorted vector ). Now as we sweep on X coordinates we keep "in" queries for left edges and "out" queries for right edges.

Stop ! Segment tree time ! In a segment tree we keep all active (ny[idx],ny[idx+1]) ( where ny denotes the normalisation vector ) segments length sum ( in the picture there would be 6 such segments ) and add to the result the distance between sweep lines * above mentioned sum. As we go , we update the segment trees at in and out queries. Again complexity O(N log N).

Let's move on to ...

Radial sweep

Basically , it would go like that:

( Don't wait , it won't load ) So , what we have here ? A line with a fixed center rotating. The 360 and 180 rotations of lines and rays are commonly used. We will apply same principles to some problems.

Maximum number of points on a line

You are given a set of N points. Find the maximum number of points on a line. For the example line AB , answer 5.

What should we start with ? Bruteforce. Let's consider we fixed a line and we want to know how many points of the N are on it. Make the equation and verify. The complexity would be O(N^3) cause we'll fix O(N^2) lines. What's slow at that ? We try the same line more times and furthermore we try all the points and that's slow.

Let's fix a point from the line. Now the line should rotate around this point , like in the picture below.

Here comes the sweep. Radial sweep. For simplicity as we fixed a point as the "center" move it to the origins along with all the other points. Now sort the points trigonometrically. ( or clockwise if you want ) Put the angles in an array. Now go through the array and count the number of points with same angle and that's it.

For the example we have point B C D E F G H. After sorting we have G B E F H D C and the angles will be the same for the sequence B E F H. So answer will be 5.

You may be asking yourself why the hack is the solution correct cause if we take B as the center we will count only 4 points. It is guaranteed that if the rightmost point from the right is taken as a center all the points on the right will be found.

Note: We could have used hashes ( that's a better complexity ) or maps ( same ) , but we insisted only on the sweep abordation.

Don't mess with the circles

Given a set of N points on a plane , determine the circle of a fixed radius R which covers the most points in S.

Now this is more tricky. Remember Shrinking Trick ? Draw a circle from each point and find out a point that is in the most circles. Let me help you with this , look :

In the given example the set is A,B,C,D,E. Point G would be good and it would cover 4 points in the set. Another useful observation is that a point in solution can be found at the intersection of at least two circles. How many intersections there are ? O(N^2). This makes an O(N^3) solution by testing any possible center with respect to all the points.

Now how we sweep this off ? Before choosing a fixed point was good , so we fix some circle. We see how it's corresponding disk interacts with other discs , so we can choose an interval that would give all the points that can be a solution for both circles. That is O(N) for each circle and we settled some intervals.

Now the problem goes as follows : given some intervals on a circle how to find a point where the intersection is maximal. We will treat them as segments. So sort them clockwise , then process them. I leave this to the reader as we do it similarly to the in-out segment procession described above. Finally , the complexity would be O(N^2 log N).

Bonus

PS:

Please state your opinion on my tutorial. Also , if you have any suggestions on what the next tutorial should be on , feel free to comment. Hope you enjoyed.

Tags geometry, sort, segment tree, line sweep

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en46 English DanAlex 2019-01-19 14:21:07 13 Tiny change: 's can help ? Well... [cut]\n\n### Li' -> 's can help? Well... [cut] \n\n### Li'
en45 English DanAlex 2016-02-07 15:40:27 6 Tiny change: ' ? Well...\n\n### Li' -> ' ? Well... [cut]\n\n### Li'
en44 English DanAlex 2015-09-18 18:43:14 8
en43 English DanAlex 2015-09-18 18:42:18 338
en42 English DanAlex 2015-09-18 11:56:57 71
en41 English DanAlex 2015-09-18 08:36:50 108
en40 English DanAlex 2015-09-18 08:21:59 0 (published)
en39 English DanAlex 2015-09-18 08:21:41 74 (saved to drafts)
en38 English DanAlex 2015-09-18 08:16:05 162
en37 English DanAlex 2015-09-17 22:22:11 12 Tiny change: 'he sweep abordation. \n\n####' -> 'he sweep approach. \n\n####'
en36 English DanAlex 2015-09-17 22:17:36 15 Tiny change: 'rmine the minimum radius circle of' -> 'rmine the circle of'
en35 English DanAlex 2015-09-17 19:22:50 28
en34 English DanAlex 2015-09-17 18:56:11 2 Tiny change: '\n#### [Bouns](https:/' -> '\n#### [Bonus](https:/'
en33 English DanAlex 2015-09-17 18:55:36 0 (published)
en32 English DanAlex 2015-09-17 18:55:28 5 Tiny change: 'le how to a point w' -> 'le how to find a point w'
en31 English DanAlex 2015-09-17 18:52:44 7 Tiny change: 'he points on the that can ' -> 'he points that can ' (saved to drafts)
en30 English DanAlex 2015-09-17 18:35:08 50
en29 English DanAlex 2015-09-17 18:31:25 172 (published)
en28 English DanAlex 2015-09-17 18:28:57 33
en27 English DanAlex 2015-09-17 18:26:07 1 Tiny change: ' algorithm. So , wha' -> ' algorithms. So , wha'
en26 English DanAlex 2015-09-17 18:23:50 45
en25 English DanAlex 2015-09-17 18:21:17 1085
en24 English DanAlex 2015-09-17 18:07:35 343
en23 English DanAlex 2015-09-17 17:45:20 1926
en22 English DanAlex 2015-09-17 17:13:20 48
en21 English DanAlex 2015-09-17 17:12:35 4
en20 English DanAlex 2015-09-17 17:12:15 954
en19 English DanAlex 2015-09-17 17:00:46 848
en18 English DanAlex 2015-09-17 16:49:04 789
en17 English DanAlex 2015-09-17 16:38:44 70
en16 English DanAlex 2015-09-17 16:37:50 138
en15 English DanAlex 2015-09-17 16:13:58 532
en14 English DanAlex 2015-09-17 16:06:55 14
en13 English DanAlex 2015-09-17 16:05:42 2 Tiny change: 'down. \n\n[](https://' -> 'down. \n\n![ ](https://'
en12 English DanAlex 2015-09-17 16:05:22 364
en11 English DanAlex 2015-09-17 16:00:12 12
en10 English DanAlex 2015-09-17 15:58:09 59
en9 English DanAlex 2015-09-17 15:55:42 38 Reverted to en7
en8 English DanAlex 2015-09-17 15:54:34 38 Reverted to en6
en7 English DanAlex 2015-09-17 15:53:14 38 Reverted to en5
en6 English DanAlex 2015-09-17 15:52:30 38
en5 English DanAlex 2015-09-17 15:48:06 464
en4 English DanAlex 2015-09-17 15:43:02 76
en3 English DanAlex 2015-09-17 15:41:49 0 Tiny change: 'ation1.gif)' -> 'ation1.gif'
en2 English DanAlex 2015-09-17 15:39:01 784
en1 English DanAlex 2015-09-17 15:37:44 935 Initial revision (saved to drafts)