Line Sweep
Algorithms
Schalk-Willem Krger 2009 Training Camp 1
presentation.start();
Closest Pair Algorithm
The problem
2008TrainingCamp2:GoodNeighbours
Theproblem:
Brucewantstovisithisfriendsonweekends.
Thefriendsarescatteredaround(eachataunique
location).
Findthetwofriendsthatliveclosesttoeachother
Maximumof1000000friends
2
Bruteforce:O(N )tooslow
Closest Pair Algorithm
Initialize h (shortest distance found so far) with the distance between the first two points.
3
h = Euclidian distance between point 1 and 2 = 6.23 units
Closest Pair Algorithm
6.44 units
h
h = Euclidian distance between point 1 and 2 = 6.23 units
No distance less than 6.23 units.
Closest Pair Algorithm
6.26 units
5.45 units
h = Euclidian distance between point 1 and 2 = 6.23 units
There are two points that are closer than the current value of h! Change h to 5.45.
Closest Pair Algorithm
4.30 units
h = Euclidian distance between point 1 and 2 = 5.45 units
Change h to 4.30 units.
Closest Pair Algorithm
C++implementation(withSTL)
#include <stdio.h>
#include <set>
#include <algorithm>
#include <cmath>
using namespace std;
#define px second
#define py first
typedef pair<long long, long long> pairll;
int n;
pairll pnts [100000];
set<pairll> box;
double best;
int compx(pairll a, pairll b) { return a.px<b.px; }
int main () {
scanf("%d", &n);
for (int i=0;i<n;++i) scanf("%lld %lld", &pnts[i].px, &pnts[i].py);
sort(pnts, pnts+n, compx);
best = 1500000000; // INF
box.insert(pnts[0]);
int left = 0;
for (int i=1;i<n;++i) {
while (left<i && pnts[i].px-pnts[left].px > best) box.erase(pnts[left++]);
for (typeof(box.begin()) it=box.lower_bound(make_pair(pnts[i].py-best, pnts[i].px-best));
it! =box.end() && pnts[i].py+best>=it->py; it++)
best = min(best, sqrt(pow(pnts[i].py - it->py, 2.0)+pow(pnts[i].px - it->px, 2.0)));
box.insert(pnts[i]);
}
printf("%.2f\n", best);
return 0;
}
Use a balanced binary tree (Set)
Time complexity: O(N log N)
7
Closest Pair Algorithm
C++implementation(withSTL)zoomedin
box.insert(pnts[0]);
int left = 0;
for (int i=1;i<n;++i) {
while (left<i && pnts[i].px-pnts[left].px > best)
box.erase(pnts[left++]);
for (typeof(box.begin()) it=
box.lower_bound(make_pair(pnts[i].py-best, pnts[i].px-best));
it!=box.end() && pnts[i].py+best>=it->py; it++)
best = min(best, sqrt(pow(pnts[i].py it->py,2.0)+
pow(pnts[i].px - it->px, 2.0)));
box.insert(pnts[i]);
}
printf("%.2f\n", best);
Time complexity: O(N log N)
8
Line segment intersections (HV)
Problem:givenasetSofNclosedsegmentsinthe
plane,reportallintersectionpointsamongthe
segmentinS
Firstconsidertheproblemwithonlyhorizontaland
verticallinesegments
Bruteforce:O(N2)time
tooslow
Line segment intersections (HV)
Useevents:startofhorizontalline,endofhorizontalline
andverticalline.
Setcontainsallhorizontallinescutbythesweepline
(sortedbyY).Indicatedasredlinesondiagram.
Horizontallineevent:add/removelinefromset.
Verticallineevent:getallhorizontallinesitcuts(get
rangefromset).Indicatedasred
dotsondiagram.
Usebalancedbinarytree(C++set)
guaranteeO(logN)foroperations.
10
Line segment intersections (HV)
// <Headers, structs, declarations, etc.>
// type=0: Starting point of horizontal line
// type=1: Ending point of horizontal line
int main () {
// <Input>
sort(events, events+e);
// Sort events by X-coordinate
for (int i=0;i<e;++i) {
event c = events[i];
// c: current event
if (c.type==0) s.insert(c.p1);
// Add starting point to set
else if (c.type==1) s.erase(c.p2); // Remove ending point from set
else {
for (typeof(s.begin()) it=s.lower_bound(point(-1, c.p1.y));
it!=s.end() && it->y<=c.p2.y; it++) // Range search
printf("%d, %d\n", events[i].p1.x, it->y);
}
}
return 0;
}
11
Line segment intersections
Moregeneralcase:linesdon'thavetobehorizontalor
vertical.
Lineschangeplaceswhentheyintersect.
Usepriorityqueuetohandleevents.
EventsalsosortedbyX.
Eventsinpriorityqueue:
endpointsoflinesegments
intersectionpointsofadjacentelements.
Setcontainssegmentsthatarecurrently
intersectingwiththesweepline.
12
Line segment intersections
Atastartingpointofalinesegment:
Insertsegmentintoset.
Neigboursarenolongeradjacent.Deletetheirintersectionpoint(ifany)
fromthepriorityqueueifitexists.
Computeintersectionofthispointanditsneigbours(ifany)andinsertinto
priorityqueue.
Atanendingpointofalinesegment:
Deletesegmentfromset.
Neigboursarenowadjacent.Computetheirintersectionpoint(ifany)and
insertintopriorityqueue.
Atanintersectionpointoftwolinesegments:
Outputpoint.
Swappositionofintersectionsegmentsinset.
Theswappedsegmentshavenewneigboursnow.Insert/deleteintersecting
13
pointsfrompriorityqueue(ifneeded).
Area of union of rectangles
Calculateareaoftheunionofasetofrectangles.
Againworkwithevents(sortedbyx)andaset(sorted
byy).
Events:
Leftedge
Rightedge
Setcontainsalltherectangles
thesweeplineiscrossing.
14
Area of union of rectangles
Knowxdistance(x)betweentwoadjacentevents.
Multiplyitbythecutlengthofthesweepline(y)toget
thetotalareaofrectanglesbetweenthetwoevents.
Dothisbyrunningthesamealgorithmrotated90degrees.
(Horizontalsweeplinerunningfromtoptobottom)
Useonlyrectanglesintheactiveset
Event:Horizontaledges.
Useacounterthatindicateshowmany
rectanglesareoverlappingatthecurrentpoint.
Cutlengthsarebetweentwoeventswherethecountiszero.
15
Area of union of rectangles
Example of inner loop
Horizontal sweep line
Vertical sweep line
xbetweentwoadjacentverticalevents
Count: 1
16
Area of union of rectangles
Example of inner loop
Count: 2
17
Area of union of rectangles
Example of inner loop
Count: 3
18
Area of union of rectangles
Example of inner loop
Count: 2
19
Area of union of rectangles
Example of inner loop
Count: 1
20
Area of union of rectangles
Example of inner loop
Count: 0
21
Area of union of rectangles
Example of inner loop
Count: 1
22
Area of union of rectangles
Example of inner loop
Count: 0
23
Area of union of rectangles
Source code (C++) can be seen on the handout.
24
Area of union of rectangles
Runtime:O(N2)withbooleanarrayintheplaceofa
balancedbinarytree(presortthesetofhorizontal
edges).
CanbereducedtoO(NlogN)withabinarytree
manipulation.
25
IOI '98: Pictures
Given:Anumberofrectangles.(0<=N<5000)
Calculatetheperimeter(lengthoftheboundaryofthe
unionofallrectangles)
Usebasicallythesamealgorithm
Horizontalboundaries:wherecountiszeroininner
loop.
26
Convex hull with sweep line
Grahamscan:Sortbyangleisexpensiveandcanget
numericerrors.(CanuseC++complexlibrary)
Simpleralgorithm:Andrew'sAlgorithm
SortbyXanduseasweepline!
Upperhull:StartatpointwithminimumXcoordinateand
moveright.Whenthelastthreepointsaren'tconvex,
deletethesecondlastpoint.Repeatuntilthelastthree
pointsformaconvextriangle.
SweeplinealgorithmrunsinO(N)
O(NlogN)(pointsaresorted)
27
Questions?
?
presentation.end();
28
