L2-Introduction to Algorithms

L2 – Introduction to Algorithms

NGEN06(TEK230) –
Algorithms in Geographical Information Systems

by: Irene Rangel, modified by Sadegh Jamali and Per-Ola Olsson 1

 L2-Introduction to Algorithms

Content

1. Overview – what is an algorithm

2. Examples of algorithms – Convex Hull
3. Computational complexity
4. Exact geometric computations
5. Choice of algorithms

2
 L2-Introduction to Algorithms

Background – what is an algorithm?

An algorithm can be seen as a set of

instructions.

These instructions use input data to provide

results of a given problem.

Input data Algorithm Result

Shortest
path
algorithm 3
 L2-Introduction to Algorithms

Algorithms have existed for a long time,

but the possibility to execute them has

been greatly improved by the introduction
of modern computers.

4
 L2-Introduction to Algorithms

Algorithm properties
All algorithms that perform the same task are not equally
good. A good algorithm should preferably have the
following properties:
1. It should always give a correct answer (or it should at
least have known limitations and guarantees of the
quality of the result).
2. It should be easy to understand and implement
3. It should be efficient.
A trade off between the properties. Most algorithms that
are easy to understand and that always give the correct
answers are inefficient. Therefore, for many applications
these intuitive, or naive, approaches cannot be used.
5
 L2-Introduction to Algorithms

Example of algorithms – convex hull

A convex hull of a point set S is the

smallest convex polygon that
covers all the points of the point set.

It can be visualized by stretching a

rubber band around all the points of
the point set.

6
 L2-Introduction to Algorithms

Convex polygon - Definition

If there are two points (p and q) inside a

polygon where the line between the
points is not entirely inside the polygon.
Then the polygon is non-convex.

If all points (p and q) inside a polygon

have a line between them that is entirely
inside the polygon. Then the polygon is
convex.

7
 L2-Introduction to Algorithms

Algorithms to compute the convex hull

We will describe 2 algorithms

that compute the convex hull of a
point set:

– Extreme Edges
– Gift wrapping

Important considerations:
- Two points are never equal
- Three (or more) points are never collinear

8
 L2-Introduction to Algorithms

Convex hull - Extreme edges

If we go in counter clockwise order along the convex hull, then
for each line segment in the convex hull it holds that ALL
points (that are not end points of the line segment) are on the
left side of the line segment.

9
 L2-Introduction to Algorithms

Convex hull - Extreme edges

If we go in counter clockwise order along the convex hull, then
for each line segment in the convex hull it holds that ALL
points (that are not end points of the line segment) are on the
left side of the line segment.

Extend the line

segment, check
that all points
are to the left.

10
 L2-Introduction to Algorithms

Convex hull - Extreme edges

Counter clockwise order, for each line segment in the convex
hull; ALL points (that are not end points of the line segment)
are on the left side of the line segment.

Three loops

for each i do j
for each j do
bool addLine = true i

for each k (not equal to i and j) do

if k is not left of the line segment then
addLine = false
if addLine
add the line segment i to j to the convex hull 11
 L2-Introduction to Algorithms

Convex hull - Extreme edges

Counter clockwise order, for each line segment in the convex
hull; ALL points (that are not end points of the line segment)
are on the left side of the line segment.
j

for each i do
for each j do
i
bool addLine = true
for each k (not equal to i and j) do
if k is not left of the line segment then
addLine = false
if addLine
add the line segment i to j to the convex hull 12
 L2-Introduction to Algorithms

Convex hull - Extreme edges

Counter clockwise order, for each line segment in the convex
hull; ALL points (that are not end points of the line segment)
are on the left side of the line segment.

One line
segment of
for each i do the convex
for each j do hull found j
i
bool addLine = true
for each k (not equal to i and j) do
if k is not left of the line segment then
addLine = false
if addLine
add the line segment i to j to the convex hull 13
 L2-Introduction to Algorithms

Convex hull - Gift Wrapping

Let us again go round the convex hull in counter clockwise order.
When we have come to a breakpoint in the convex hull we can
make the following identification:

The change of direction is smaller to the

next point in the convex hull than to any
other point in the point set.

The problem is to find the first line segment in the convex hull.
This is normally solved by starting a horizontal line that passes
through the lowest point.
14
 L2-Introduction to Algorithms

Convex hull - Gift Wrapping

find the lowest point (smallest y-coordinate), denote this point as start point
set the start point as point i
define a horizontal line that starts in x=0 and ends in point i
repeat
for each point j not equal to point i
Compute counterclockwise angle from previous edge
let k be the index of the point with the smallest angle.
add line segment i to k to the convex hull
denote point k as i
until point i is equal to the start point

Start point
(first i)
i
15
 L2-Introduction to Algorithms

Convex hull - Gift Wrapping

find the lowest point (smallest y-coordinate), denote this point as start point
set the start point as point i
define a horizontal line that starts in x=0 and ends in point i
repeat
for each point j not equal to point i
Compute counterclockwise angle from previous edge
let k be the index of the point with the smallest angle.
add line segment i to k to the convex hull
denote point k as i
until point i is equal to the start point

First line segment

of the convex hull
i

16
 L2-Introduction to Algorithms

Computational complexity
How can we measure the efficiency of an algorithm?

Computational complexity

Computational complexity can refer to processing step

(time) in relation to the size of the input data i.e.
computational complexity of processing time.
Computational complexity can also refer to computer
memory.

17
 L2-Introduction to Algorithms

Computational complexity
Here computational complexity refers to processing step
(time) in relation to the size of the input data.

Plotting the number of time steps as a function of number

of points.

18
 L2-Introduction to Algorithms

Computational complexity
The computational complexity of the algorithm is said to be
O(f(n)) if there exists a constant C and an integer n0 such that
C*f(n)  g(n) for all n > n0.
g(n) = “actual” processing time
n = amount of input data

(The notation O(…) is read “ordo”).

19
 L2-Introduction to Algorithms

Computational complexity
Why use O(f(n)) instead of g(n)?
- g(n) is maybe unknown.

- The “exact” time is less important. The main importance is to

know how the number of steps will increase when the amount of
input data increase.

20
 L2-Introduction to Algorithms

Computational complexity

O(1) Constant time Independent of input (very fast)

O(log n) Logarithmic time Fast
O(n) Linear time Fast or moderate
O(n*log n) Sub-linear time Fast or moderate
O(n2) Quadratic time Moderate
O(nk) Polynomial time (also O(n2) is Slow
K3 in polynomial time)
O(kn) Exponential time Intractable (difficult)

21
 L2-Introduction to Algorithms

Computational complexity

O(1) Constant time Independent of input (very fast)

O(log n) Logarithmic time Fast
O(n) Linear time Fast or moderate
O(n*log n) Sub-linear time Fast or moderate
O(n2) Quadratic time Moderate
O(nk) Polynomial time (also O(n2) is Slow
K3 in polynomial time)
O(kn) Exponential time Intractable (difficult)

22
 L2-Introduction to Algorithms

Computational complexity

O(1) Constant time Independent of input (very fast)

O(log n) Logarithmic time Fast
O(n) Linear time Fast or moderate
O(n*log n) Sub-linear time Fast or moderate
O(n2) Quadratic time Moderate
O(nk) Polynomial time (also O(n2) is Slow
K3 in polynomial time)
O(kn) Exponential time Intractable (difficult)

23
 L2-Introduction to Algorithms

Computational complexity

O(1) Constant time Independent of input (very fast)

O(log n) Logarithmic time Fast
O(n) Linear time Fast or moderate
O(n*log n) Sub-linear time Fast or moderate
O(n2) Quadratic time Moderate
O(nk) Polynomial time (also O(n2) is Slow
K3 in polynomial time)
O(kn) Exponential time Intractable (difficult)

24
 L2-Introduction to Algorithms

Computational complexity

O(1) Constant time Independent of input (very fast)

O(log n) Logarithmic time Fast
O(n) Linear time Fast or moderate
O(n*log n) Sub-linear time Fast or moderate
O(n2) Quadratic time Moderate
O(nk) Polynomial time (also O(n2) is Slow
K3 in polynomial time)
O(kn) Exponential time Intractable (difficult)

25
 L2-Introduction to Algorithms

Computational complexity

26
 L2-Introduction to Algorithms

Computational complexity

O(1) Constant time Independent of input (very fast)

O(log n) Logarithmic time Fast
O(n) Linear time Fast or moderate
O(n*log n) Sub-linear time Fast or moderate
O(n2) Quadratic time Moderate
O(nk) Polynomial time (also O(n2) is Slow
K3 in polynomial time)
O(kn) Exponential time Intractable (difficult)

27
 L2-Introduction to Algorithms

Computational complexity

O(1) Constant time Independent of input (very fast)

O(log n) Logarithmic time Fast
O(n) Linear time Fast or moderate
O(n*log n) Sub-linear time Fast or moderate
O(n2) Quadratic time Moderate
O(nk) Polynomial time (also O(n2) is Slow
K3 in polynomial time)
O(kn) Exponential time Intractable (difficult)

Be aware of that what is regarded to be fast , moderate, etc. is dependent on

what kind of algorithm that is considered.

For example an O(n*log n) – algorithm can be fast for certain applications (e.g.
sorting routines), but slow for other purposes (e.g. search).
28
 L2-Introduction to Algorithms

NP-complete problems

Problems for which no polynomial time algorithm have

been found. Exponential time algorithms are in most
cases too slow for practical use so other solutions must
be introduced.

For example the travelling salesman problem:

Finding the shortest route that visits all nodes in a network

Checking all possible

combinations?

29
The route was generated by the website Reil (2005).
 L2-Introduction to Algorithms

Heuristic

How to make an algortihm more efficient?

A heuristic is a rule of thumb that could be used for

increasing the computational speed of algorithms.

With a heuristic the algorithm is not guaranteed to

give the correct answer (but a good heuristic will lead
to an answer of the algorithm with satisfying quality).
Heuristic for the travelling
salesman problem:
Always visit the closest city that is
not already visited.
30
 L2-Introduction to Algorithms

Analyses of computational complexity

How to estimate the computational complexity?

Here worst case scenario

- Analyze the code, especially nested loops.

- Implement and test.

31
 L2-Introduction to Algorithms

Analyses of computational complexity

• Extreme Edges O(n3)
for each i do
for each j do
bool addLine = true
for each k (not equal to i and j) do
if k is not left of the line segment then
addLine = false
if addLine
add the line segment i to j to the convex hull

Three loops
that in worst
case iterates
over “all” points

32
 L2-Introduction to Algorithms

Analyses of computational complexity

• Gift Wrapping O(nh) or O(n2) Convex hull with small
n = number of points number of edges:
h = number of edges in the convex hull Large difference
between h and n
find the lowest point (smallest y-coordinate), denote this point as start point
set the start point as point i
define a horizontal line that that starts in x=0 and ends in point i
repeat
for each point j not equal to point i
Compute counterclockwise angle from previous edge
let k be the index of the point with the smallest angle.
add line segment i to k to the convex hull
denote point k as i
until point i is equal to the start point

33
 L2-Introduction to Algorithms

Analyses of computational complexity

• Extreme Edges O(n3)

• Gift Wrapping O(nh) or O(n2)
Processing time (s)

40
30
Gift wrapping
20
Extreme edges
10
0
10 30 50 70 90
Input points

34
 L2-Introduction to Algorithms

Exact geometric computations

To represent coordinates in a computer we have to
discretize the plane (we are not using real coordinates,
but rational coordinates).

Grid is
fraction of
millimeters.

The accuracy is higher than the accuracy of the data i.e. for
computations of area, length computations etc. the grid is
sufficiently dense…. 35
 L2-Introduction to Algorithms

Exact geometric computations

….but it is difficult to define what we mean by saying that a
point lie exactly on a line.

In this case the line can not

be straight and pass point b.

Treatment of cases where a point is on a line segment is

done in the field of exact geometric computations. This is a
theoretical subject that is outside the scope of this course.
36
 L2-Introduction to Algorithms

Choice of algorithms
Computational complexity describes the worst case scenario.
For example extreme edges:

Highest efficiency not always best:

Algorithms with high efficiency can be slow for smaller data
sets and very difficult to implement.
Algorithms with heuristics do not (always) give a correct result.
37
 L2-Introduction to Algorithms

Choice of algorithms
Computational complexity describes the worst case scenario.
For example extreme edges:

Highest efficiency not always best:

Algorithms with high efficiency can be slow for smaller data
sets and very difficult to implement.
Algorithms with heuristics do not (always) give a correct result.
38
 L2-Introduction to Algorithms

Choice of algorithms
Computational complexity describes the worst case scenario.
For example extreme edges:

Heuristic for the travelling

salesman problem:
Always visit the closest city that is
not already visited.

Highest efficiency not always best:

Algorithms with high efficiency can be slow for smaller data
sets and very difficult to implement.
Algorithms with heuristics do not (always) give a correct result.
39
 L2-Introduction to Algorithms

Choice of algorithms
What algorithm is used?

Is a distance from a polygon to a point from the boundary or

from the centroid?

Vector to raster, how are cell values derived?

40
 L2-Introduction to Algorithms

A note on coordinate systems

In these lecture notes a standard two-dimensional Cartesian
coordinate system is used:

This implies the Earth surface is projected on a planar surface.

All map projections distort some of the geometric properties
(distances, angles etc.). For small areas the approximations are
good, but not for larger regions (e.g. don’t use the polygon area
algorithm in lecture notes 4 for the area of an entire country).

x-axis is East and y-axis is North. Geodetic reference systems

sometimes have x-axis as North. 41