Transcript powerpoint

Data Structures and
Algorithms (AT70.02)
Comp. Sc. and Inf. Mgmt.
Asian Institute of Technology
Instructor: Prof. Sumanta Guha
Slide Sources: CLRS “Intro. To
Algorithms” book website
(copyright McGraw Hill)
adapted and supplemented
CLRS “Intro. To Algorithms”
Ch. 33: Computational Geometry
If p1 = (x1, y1) and p2 = (x2, y2) then
p1  p2 = x1 x2
y1 y2
= x1y2 – x2y1*
If p1  p2 > 0, then p1 is clockwise from p2 (turning around the origin);
if p1  p2 < 0, then p1 is counterclockwise from p2;
If p1  p2 = 0, then p1 and p2 are collinear (pointing in either same or
opposite directions)
*
The cross product is actually a 3D vector whose magnitude is |x1y2 – x2y1|. Here we simplify for 2D.
If DIRECTION(pi, pj, pk) > 0, then pj – pi is a left turn from pk – pi around pi
< 0, then pj – pi is a right turn from pk – pi around pi
= 0, then pj – pi and pk – pi are collinear
How?!

Eliminate the polar co-ordinate sort part of Graham’s scan by
modifying it to scan the vertices sorted from left to right.
Otherwise, the underlying principle, data structures, etc. remain
the same.
Comment : This modification of Graham’s scan was made by
Andrew (1979) and is often called the Monotone Chain
algorithm.
Jarvis’s march is output-sensitive!
Closest Pair by Divide-and-Conquer
Following slides are copied from Dariusz
Kowalski
(www.csc.liv.ac.uk/~darek/COMP523/le
cture5.ppt)
Solution
Preprocessing:
 Sort points according to the first coordinate (obtain
horizontal list H) and according the second coordinate
(obtain vertical list V)
Main Algorithm:
 Partition list H input into halves in linear time (draw
vertical line L containing medium point)
 Solve the problem for each half of the input
separately, obtaining two pairs of closest points; let 
be the smallest distance from the obtained ones
 Find if there is a pair which has distance smaller than
 - if yes then find the smallest distance pair
Lecture 5: Divide and Conquer,
cont. (Dariusz Kowalski)
13
Main difficulty
Find if there is a pair which has distance smaller
than  if yes then find the smallest distance pair
How to do it in linear time?



Lecture 5: Divide and Conquer,
cont. (Dariusz Kowalski)
14
Closest pair in the strip
1. Find a sublist P of V
containing all points with
a distance at most 
from the line L - in linear
time
2. For each element in P
check its distance to the
next 8 elements and
remember the closest
pair ever found
Lecture 5: Divide and Conquer,
cont. (Dariusz Kowalski)



L
15
Why to check only 8 points
ahead?
1. Partition the strip into
squares of length /2 as

shown in the picture.
2. Each square contains at
/2
most 1 point - by
definition of .
3. If there are at least 2
squares between points
then they can not be the
closest points.
4. There are at most 8
squares to check. Lecture 5: Divide and Conquer,
cont. (Dariusz Kowalski)
/2
/2
/2
/2
/2
L
16
Problems








Ex. 33.3-2
Ex. 33.3-4
Ex. 33.3-5
Ex. 33.3-6
Ex. 33.4-3
Ex. 33.4-4
Ex. 33.4-5
Prob. 33-1