Geometric
Algorithms
· Lecturer : John Bourke
bourkejoymath.
Muni .z
·
Each week : I
algorithm
It exercise on board
Together at end
,
if possible)
·
Interconnected :
eg sweepline algorithm in W]
is used in
many
later
algorithms
·
Elearning course (see
learning materials
for link
·
Upload notes
weekly to IS
·
Book :
Computational geometry
by de
Berg
·
Exam at end.
List
of algorithms
Convex hull
Line intersection
(sweepline
Map overlay
PolygontriangulationHalf-plane
intersection
↑
↑
Linear
programming &
Orthogonal range searching
Point location
Voronoi
diagrams (Patofia
Delauney Triangulation
Lecture) Convex
hell in the plane
· KSIR" (the plane is convex
if
for all p,
gEK ,
the
line
segment p is also in K.
(Note p contains points of form
·
(~ =
p +
x(q
p)
for x[0 ,
1)
Convex
·
Non-convex
vexHull
Let PSIR" 2
CH(P) : = smallest convex set
containing
convex hall p
We have obvious formula
CH(P) =
1 is
.
intersection of
* convex all convex sets
PS
containing p
but not
computationally usefulsince can be
infinitely many convex sets
containing P.
Goal :
compute CHIP) for P finite
P finite = CHIP) a convex
polygon :
is. bounded
by finitely manyV
&
straight-line segments.
Convex
Polygons Non-convex polygons
# An
# ForPrintea
S Pet a h plane
half planes points on
containing 2 points of p
one
side
of a
straightline
Goal :
compute CHIP) for P finite
For P finite,
CH(P) =
NH
Pet a h plane
containing 2 points of p
Example : P CH(p)
Pr
&
· P7
Pi &
&
P3&
PS
O
⑧ P4
·
pa
·
ps
·& PG
Plo
Idea for simple algorithm :
search
for directed live
segments p onconvex
hull in clockwise order
>
-
>
eg. PIP2 , P2P7,
-
-
a
directed line
segment will lie
on pointof b lie o
When does point r lie to leftof g?
r
Consider
q
do turning anticlockwise
P
· Thenw lies to left
of pi)
0 <
-1800
·
This happens #S det
(9XPX
~ = 10 ,
1)
·
Eg.
L de) !) =
10
20
= 90
p = 10
,
0)
7
q
=
4,
0)
So constant time operation to
-
>
check ifa lies to left of q
Algorithm : Slow Convex tull(p
·
For each
p ,
gEP,
test if no other
point of p lies to left
of pig.
· If so
,
add
pet to list↓
· Sort clockwise can be done in
(Time
Oculogne
(whereis no of
pls
Complexity· n(n-1) distinct pairs of points.
·
For each such pair ,
check
n-2 pts (if they lie to left)
so
complexity
O(n(nV(n-2)
+ nlogn) =
0(n)
Faster
algorithm
: Graham's scan
Onlogn/
· Order points of Plexicographically
:
(Fright
ic .
p
<
q)Pxgx or (px =
qx
&
py >
gu)
· Obtain ordered
sequence P ,< Pz ......
Pn .
-- upper hull
- Pi
Pn
= --~ lower hall
·
p, pr lie on convex hull &
·
Convex hull splits in 2 parts :
upper
hul & erhull.Goal
: search for upper hull,then
lower hull.
Finding upper
hull
·
Li :=
upper
hall for Epi, Pr, .-., Pi
·
d =
Epipz2.
·
Given L; construct Litt
-
add
pil,
which must
belong to Litt.
-> consider last 3
pts (pj ,
pi ,
pit) in Litt.
Say they form a
right turn if
Pitt lies to the
right of T (i.
det()0
Pi
Pj
XXPitt
-
If
they form a
right turn ,
we
stop.
Finding upper
hull ctd
·
If not
,
delete middle of 3 pts
pi from Lit (e .
p; [p:**)
·
Then look at last 3 pts in
Lit &
repeatThis step until :
last
3 pts form a
right turn or
only 2 pts remain .
·
In this
way,
obtain
Lupper = In
End
of algorithm
·
Lower is calculated
similarly :
is .
Calc .
lower hulls
of
SpacipuS , Spun,Papat,
- - .
, Spic--, pas
·
Finally append Lower to tupper
(firstly delete p, , on from Lower
Time
Complexity Onlogn/
·
Order n pts lexicographically
Takes
Inlogn/ eg .
mergesort
·
On
upper
hull , constant time
to add/remove a
pt.
·
Each pt added & removed at
most one
.
At mostIn actions
·
On lower hull
,
also In
--
·
Append lists
:
O(5nthlogn-nlogn)
Another
algorithm
: Gift
wrapping
·
Useful if know in advance , no
of pts
on convex hull SK ,
where
is small compared to n.
6
C
E
e
& ·
a
-
O
Another
algorithm
: Gift
wrapping
·
Useful if know in advance , no
of pts
on convex hull SK ,
where
is small compared to n.
6
C
E
e
& ·
p ,
o
-
O
·
Find leftmost point p. .
Another
algorithm
: Gift
wrapping
·
Useful if know in advance , no
of pts
on convex hull SK ,
where
is small compared to n.
Pa
..--
O
·
Find leftmost point p. .
·
Draw lines to other pts , Scherov
one
of greatestslope.
Endpoint pr.
-
Another
algorithm
: Gift
wrapping
·
Useful if know in advance , no
of pts
on convex hull SK ,
where
is small compared to n .
...
·
Find leftmost point p. .
·
Draw lines to other pts , Scherov
one
of greatestslope.
Endpoint 2.
·
Draw lines to remaining pts & choose ⑬
so <
pipups is
largest.
Another
algorithm
: Gift
wrapping
·
Useful if know in advance , no
of pts
on convex hull SK ,
where
is small compared to n.
6
oo
P ,
o
ine
-
op4
·
Find leftmost point p. .
·
Draw lines to other pts , Scherov
one
of greatestslope.
Endpoint 2.
·
Draw lines to remaining pts & choose ⑬
so <
pipups is
largest.
·
Repeat until return to P1.
Another
algorithm
: Gift
wrapping
·
Useful if know in advance , no
of pts
on convex hull SK ,
where
is small compared to n .
6
·4
·
Find leftmost point p. .
·
Draw lines to other pts , Scherov
one
of greatestslope.
Endpoint 2.
·
Draw lines to remaining pts & choose ⑬
so <
pipups is
largest.
·
Repeat until return to P1.
Another
algorithm
: Gift
wrapping
·
Useful if know in advance , no
of pts
on convex hull SK ,
where
is small compared to n.
6
·4
·
Find leftmost point p. .
·
Draw lines to other pts , Scherov
one
of greatestslope.
Endpoint 2.
·
Draw lines to remaining pts & choose ⑬
so <
pipups is
largest.
·
Repeat until return to P1.
·
Complexity
Exercise
·
Apply Graham's scan to cale .
convex hall
g
8
&
&
&
⑧
-
&
⑧
o