BCSE204L- Design and

Analysis of Algorithms

Dr. Iyappan Perumal

School of
Computer Science & Engineering
VIT,Vellore.
 Module 5 : Geometric Algorithms (4
Hours)

⚫ Line Segments, Properties,

Intersection, Sweeping Lines
⚫ Convex hull finding Algorithm
⚫ Graham’s Scan
⚫ Jarvis March Algorithm

◦ .
Computational Geometry
⚫ Branch of computer science that studies
algorithms for solving geometric problems.
⚫ Used in various fields such as computer graphics,
robotics, VLSI design, computer-aided design, molecular
modelling, metallurgy, manufacturing, Textile layout,
forestry and statistics.
⚫ Input to Computational Geometry Problem
◦ Set of geometric objects such as a set of points, a set of line
segments, or the vertices of a polygon in counter clock- wise
order.
⚫ Output to Computational Geometry Problem
◦ Response to a query about the objects such as whether any of
the lines intersect, or perhaps a new geometric object, such as
the convex hull (smallest enclosing convex polygon) of the set
of points.
Computational Geometry
⚫ Here Problems are represented in 2D- i.e in the plane
⚫ Represents each input object by a set of points
{p1,p2,p3………} where each pi =(xi,yi) and xi,yi
belongs to Real numbers.
⚫ For example, we represent an n-vertex polygon P by
a sequence (po,p1,p2, … … … . pn-1)of its vertices in
order of their appearance on the boundary of P.

⚫ Note: Able to apply in 3D as well as higher dimensional

spaces, such problems and their solutions can be very
difficult to visualize.
 Basic Geometric Objects in the Plane

Point :denoted by a pair of coordinates (x,y)

Segment :Portion of a straight line between two points

Polygon : circular sequence of points (vertices) and

segments (edges)
Line Segments
⚫ Basic Questions about Line segments and how to
answer??
⚫ Whether one segment is clockwise or counter
clockwise from another that shares an endpoint
⚫ which way we turn when traversing two adjoining
line segments,
⚫ and whether two line segments intersect??
◦ Sweeping – to determine whether set of line
segments contain any intersections.
◦ Rotational Sweep-Computation of Convex hull
(Smallest enclosing convex polygon of set of n
points)
◦ Graham’s Scan & Jarvis March
Line and Line Segments
Line Line Segment

• No definite Endpoints • Definite Endpoints

• Extended in both the • Can Extend but not in both

directions the direction
• Length of the line is indefinite • Length of the line is definite

• Has no start or end point • Has both start and end point

Convex Combination : A convex combination of two

distinct points p1(x1,y1) and p2(x2 ,y2) is any point
p3(x3,y3) such that for some α in the range 0 ≤ α ≤ 1,
we have x3 = αx1 +(1− α)x2 and y3 = αy1 + (1−
α)y2 . We also write that p3 = αp1 + (1 − α)p2.
Line Segments- observation
⚫ P3 is any point that is on the line passing
through p1 and p2 and is on or between p1
and p2 on the line.
⚫ Given two distinct points p1 and p2 , the line
segment p1p2 is the set of convex
combinations of p1 and p2.
⚫ We call p1 and p2 are the endpoints of
segment p1 p2
⚫ Sometimes the ordering of p1 and p2 matters,
and we speak of the directed segment p1p2 .
If p1 is the origin(0,0), then we can treat the
directed segment p1p2 as the vector p2 .
Questions related to Line Segments
⚫ Given two directed segments p0p1 and p0p2 , is
p0p1 clockwise from p0p2 with respect to their
common endpoint p0 ? If I have to
reach p0p2
from p0p1
p2 which is nearer-
clockwise or
counter
p1 clockwise

po p2

P0p2 is counter clockwise from pop1-

left turn at p1
Questions related to Line Segments
⚫ Given two line segments p0p1 and p1p2 , if we
traverse p0p1 and then p1p2 , do we make left or right
turn at point p1??
p2

p1
p2

po

For above case: – Left Turn

Questions related to Line Segments
⚫ Do line segments p1p2 and p3p4 intersect??

P2(x2,y2)

P3(x3,y3)

P4(x4,y4)
P1(x1,y1)

Note:There are no restrictions on the given points

Line Segments Properties
⚫ To handle above Questions some tools are used:

⚫ Tool 1:Vector representation

⚫ A vector p0p1 with p0 =(0,0), can be written as p1 .

Line Segments Properties- cross products

Cross product p1*p2 gives as the signed area of the

parallelogram formed by the points 0,0, p1, p2 , and
p1+p 2 =(x1+x2, y1+y2). • If p1*p2 = +ve, p1 is clockwise
from p2 with respect to origin.
p1*p2 = Det x1 x2
y1 y2 • If p1*p2 < 0, p1 is counter
clockwise from p2
= x1y2-y1x2 • If 0, its colinear,pointing in
either same or opposite
direction
Line Segments Properties- cross products
p2-p0
p2

p1-p0
p1

po

We let consider p1 - p0 denote the vector

p11=( x11, y11) where x11=x1-x0 and y11=y1-y0 and we
define p2-p0 similarly as p21=( x21, y21) .
Now Cross product is calculated as:

p11 * p21 = (p1-p0) *(p2-p0)

x1-x0 x2-x0
= Y1-y0 y2-y0
Line Segments Properties

Using the cross product to determine how consecutive line

segments p0p1 and p1p2 turn at point p1 .

By checking whether the directed segment p0p2 is

clockwise or counter clockwise relative to the directed
segment p0p1 .
(a) If counter clockwise, the points make a left turn.
(b) If clockwise, they make a right turn.
Line Segments Intersection
Line Segments Intersection
Returns true if points
intersect

Rotation using cross

product method

Determines whether a
point known to be
colinear with a segment
lies on that segment.
Comp 163: Computational Geometry Professor Diane Souvaine
Tufts University, Spring 2005 Scribe: Kevin Keating

L i n e Segment Intersection U s i n g a Sweep Li n e

A l go r i t hm

1 Introduction
Given a set of n line segments, how would you compute all intersections be-
tween these segments? To naively check each line segment for an intersection
with every other line segment would require O(n 2 ) time. However, this may
do unnecessary work, as it is possible that many segments do not intersect.
It will also return the intersections in unsorted order
An alternative approach is to use a plane sweep algorithm. Such an
algorithm moves a line across the plane to find intersection points. Imagine
the sweep line moving rightward across the plane. All intersections to the
left of the sweep line have already been detected. The status of this sweep
line is the set of segments currently intersecting it. This status changes as
the sweep line moves to the right. Any time the sweep line passes over an end
point of a segment or an intersection point, the sweep line stops and updates
this status. Thus, these points are called the stopping points. Because the
stopping points are processed in sorted order, the intersections are found in
sorted order.
We are concerned with finding intersections of line segments currently on
the sweep line. However, two line segments can not intersect unless they are
next to each other. Thus, we keep track of the vertical ordering of the line
segments and only test neighboring segments for intersection.

2 Overview
Given: n line segments defined by 2n endpoints.

Goal: Compute all intersections.

Status Dat a Structure:

1
 Figure 1: A sweep line at x = s.

This stores the cross section of the arrangement of line segments inter-
secting the sweep line at x = s for some value of s. The invariant is that
all intersections to the left of x = s have already been computed and re-
ported. s is initialized at − ∞ , where the status data structure contains no
line segments.

Stopping Points Dat a Structure:

This data structure contains start and end points of all line segments that
are to the right of x = s. In addition, it contains intersection points to the
right of the sweep line for line segments which are currently adjacent.

3 D a t a Structure Specifics
1. Status D a t a Structure
This structure stores the slope, y-intercept, start point, and end point for each
line segment on the status line. The segments are ordered by their vertical
position (their y-coordinate at x = s). It is implemented as a balanced binary
search tree allowing:

2
 • Insertions in O(log n) time

• Deletions in O(log n) time

• Finding the neighbors of a segment in O(log n) time

In addition, when two segments are no longer neighbors, their intersection

point must be removed from the stopping points data structure. To quickly
locate any such intersection points, there is a pointer from the segments in
the status data structure to their intersection point in the stopping points
data structure.

Figure 2: The status data structure stores slope, y-intercept, start point, and
end point for each line on the status line.

2. Stopping Points D a t a Structure

This structure stores all stopping points, as well as indicating the type of
stopping point: segment start point, segment ending point, and intersection
point. This structure uses a priority queue, implemented as a heap, allowing:

• The point with the minimum x-coordinate to be removed in O(log n)

time.

• A new point to be inserted in O(log n) time.

• An intersection point to be deleted in O(log n) time. This occurs when

two line segments are no longer neighbors.

3
 • The structure to be initialized with all segment start and end points.
This can be done in O(n) time if the heap is built bottom up.

Figure 3: The stopping points data structure implemented as a heap.

4 P lane Sweep
To perform the plane sweep, remove and process the next event point from
the stopping points data structure.

At a line segment starting point:

• Do binary search to insert the segment into the status data structure.

• Notify the neighbors that they are no longer adjacent and delete their
intersection point (if any) from the stopping points data structure.

• Compute the intersections of this segment with its neighbors (if any)
and insert those into the stopping points data structure.

At a line segment ending point:

• Delete the segment from the status data structure.

• Notify the neighbors of the deleted segment that they are now adjacent.
Compute their intersection point (if any) and insert it into the stopping
points data structure.

4
At an intersection point:

• Output the point.

• Swap the positions of the intersecting segments in the status data struc-
ture.

• Notify the new neighbors of the swapped segments. Insert and delete
intersection points from the stopping points data structure as needed.

The algorithm finishes when the stopping points data structure is empty.
It outputs all intersection points sorted by x-coordinate.

5 Com plexity
1. Naive A l go r i t hm
Brute force calculation of all intersections requires O(n 2 ) space and O(n 2 )
time. If the output must be later sorted, then the total runtime will be
O(n 2 log n)

2. Space C o m p lexi ty
The status data structure contains at most one line for each of the n lines in
the problem, so it is O(n). In the stopping points data structure, there can
be n starting points and n end points. In addition, because only adjacent
lines can have intersection points, there can be at most n − 1 intersection
points. Thus, stopping points is also O(n). Therefore, the algorithm has
O(n) space complexity.

3. T i m e Complexity
The plane sweep algorithm is output sensitive. That is, the running time
depends on the number of intersection points in the graph. Let k equal the
number of intersection points in the graph. Plane sweep runs in O((n +
k) log n) time, while the naive algorithm would require O(n 2 ). Thus, plane
sweep normally results in a faster runtime. However, k can be as big as O(n 2 )
if all line segments intersect, resulting in a run time of O(n 2 log n).
The run time is computed as follows:

5
 The stopping points data structure can be initialized in O(n) time, as the
heap is built bottom up. The status data structure is initialized in constant
time, as there are no line segments at x = − ∞ .
Each point in the stopping points data structure must be processed. This
includes one starting and one stopping point for each line segment, as well as
one point for each intersection point. Thus, there are O(n + k) points that
must be processed.
As shown above, finding the next stopping point can be found in O(log n).
This point can be either a starting point, an ending point, or an intersection
point.

Starting points can be processed in O(log n) time:

• The new segment is inserted into the status data structure in O(log n)
time.
• The neighbors of the new segment are no longer adjacent, so their
insertion point is deleted. Because there is a pointer from the seg-
ments in the status data structure to the intersection point in the stop-
ping points data structure, finding the intersection point takes constant
time. Deleting this point takes O(log n) time.
• The intersection points of the new segment with its neighbors are com-
puted and inserted into the stopping points data structure. These
insertions take O(log n) time each.

Stopping point can be processed in O(log n) time:

• The segment is deleted from the status data structure in O(log n) time.
• The intersection point of the neighbors of the deleted segment is in-
serted into the stopping points data structure in O(log n) time.

Intersection point can be processed in O(log n) time:

• The segments are swapped in the status data structure in O(log n)
time.
• Up to two intersection points may be deleted and up to two intersection
points may be added to the status data structure. This is done in
O(log n) time.

6
 Thus, any point may be processed in O(log n) time. As there are O ( n + k )
points, the overall algorithm runs in O((n + k) log n) time.

6 Lines
The plane sweep algorithm can be modified to calculate the intersections of
lines, rather than line segments.
The status data structure must now be initialized at x = − ∞ with all
lines in order of decreasing slope. Because lines never need to be inserted or
deleted, this data structure may be implemented as an array.
The stopping points data structure no longer contains starting or end
points. Instead, it must be initialized with intersections points of lines adja-
cent at x = − ∞ .

Figure 4: An arrangement of lines and the intersections of neighbors

7
 Module 5 : Geometric Algorithms (4
Hours)

⚫ Line Segments, Properties,

Intersection, Sweeping Lines
⚫ Convex hull finding Algorithm
⚫ Graham’s Scan
⚫ Jarvis March Algorithm

◦ .
Convex Hull

Problem Statement: Having set of points , our

objective is to draw the convex polygon, How it should
be?? - All points should be covered – either inside
polygon or in the boundary.
Note: No .of points >=3 and points should not be in
collinear
Convex Hull

p6
p5

p4

p7

p3 p9
p2

p1
p8
Convex Hull- Definition
⚫ The convex hull of a set Q of points, denoted
by CH(Q) is the smallest convex polygon P for
which each point in Q is either on the
boundary of P or in its interior.
⚫ Note : All points in the set Q are unique and
that Q contains at least three points which are
not colinear.
⚫ Vertices maximizes the area while minimizing
the circumference.
Graham’s Scan
⚫ Start at point guaranteed to be on the hull. (the point
with the minimum y value i.e lowest y coordinate).
⚫ Sort remaining points by polar angles of vertices relative
to the first point.
⚫ Go through sorted points, keeping vertices of points
that have left turns(turn related to the previous 2 points)
and dropping points that have right turns.
Graham’s Scan
• Iterate in the sorted order,
placing each point on the
stack, but only if it makes a
counter clockwise turn
relative to the previous two
points on the stack

• Pop previous point off of

the stack if making a
clockwise turn.
Graham’s Scan
Graham’s Scan

STACK

2
0
1
0
Graham’s Scan

3
2
1
0
Graham’s Scan

4
3
2
1
0
Graham’s Scan

4 Pop
out
3
2
1
0
Graham’s Scan

3
2
1
0
Graham’s Scan

5
2
1
0
Graham’s Scan

6
5
2
1
0
Graham’s Scan

6
5
2
1
0
Graham’s Scan

5
2
1
0
Graham’s Scan

2
1
0
Graham’s Scan
Algorithm – Time Analysis

N – O(n)
O(1) time for
finding polar
angle
Sorting of n
points- (n log n)

O(1) time for all O(1)

push operation

O(n)
n- push
operations
m<= n-1 - pop
operations

Overall - O(n logn)

 Module 5 : Geometric Algorithms (4
Hours)

⚫ Line Segments, Properties,

Intersection, Sweeping Lines
⚫ Convex hull finding Algorithm
⚫ Graham’s Scan
⚫ Jarvis March Algorithm

◦ .
Some Terminologies
⚫ Polygon: Curve ending on itself that is formed by a
sequence of straight-line segments, called the sides of
the polygon.
⚫ Convex Set: A set of points on plane is called convex
if for any 2 points P and Q, the entire line segments
with end points P and Q belongs to the set.
⚫ Vertex: A point joining two consecutive sides is a of
the polygon.
⚫ Boundary- Set of points on the polygon itself.
⚫ Interior- Set of points in the plane enclosed by a
Simple polygon.
⚫ Exterior- set of points surrounding polygon.
⚫ Convex Polygon- Given any two points on the
boundary or interior of a simple polygon, all points on
the line segment drawn between them are contained in
the polygon’s boundary or interior.
Convex Hull

Problem Statement: Having set of points , our

objective is to draw the convex polygon, How it should
be?? - All points should be covered – either inside
polygon or in the boundary.
Note: No .of points >=3 and points should not be in
collinear
Convex Hull

p6
p5

p4

p7

p3 p9
p2

p1
p8
Convex Hull- Definition
⚫ The convex hull of a set Q of points, denoted
by CH(Q) is the smallest convex polygon P for
which each point in Q is either on the
boundary of P or in its interior.
⚫ Note : All points in the set Q are unique and
that Q contains at least three points which are
not colinear.
⚫ Vertices maximizes the area while minimizing
the circumference.
Jarvis’s March /Gift Wrapping algorithm
⚫ Computes the convex hull of a set Q of points by a
technique known as package wrapping (or gift wrapping).
⚫ Algorithm runs in O(n h) time.
⚫ h-> number of vertices of CH(Q)
Jarvis’s March

⚫ Choose the first vertex as the lowest point p0

⚫ Next vertex p1, has the smallest polar angle of any point with respect
to p0,Then, p2 has the smallest polar angle with respect to p1.
⚫ Right chain goes as high as the highest point p3.
⚫ Then, we construct the left chain by finding smallest polar angles with
respect to the negative x-axis.
Jarvis’s March
⚫ Algorithm:
⚫ Find a point p1 on the convex hull (e.g. the
lowest point).
⚫ Rotate counterclockwise a line through p1 until it
touches one of the other points (start from a
horizontal orientation).
⚫ Question: How is this done ?

• Repeat the last step for the new point.

• Stop when p1 is reached again.
Time Complexity: O(nh), where n is the input size and h
is the output (hull) size.
131.
Thank you