Transcript A 1

Computational Geometry
The art of finding algorithms for solving geometrical problems
• Literature:
– M. De Berg et al: Computational Geometry,
Springer, 2000.
– H. Edelsbruner: Algorithms in
Combinatorial Geometry, Springer, 1987.
1. Convex Hull
1.1 Euclidean 2-dimensional space E2
– Real Vector Space V2 (V,+,•);
– Equations of lines in E2:
a1x1 + a2x2 = b
X=  A + (1- ) B
(eq. 1)
(eq. 2)

(1-)
A
X
B
1.2 Affine / Convex Combination
Affine combination of points A and B
 A + m B,
+ m = 1
Convex combination of points A and B
 A + m B,
+ m = 1,
, m  0
Generalization: Euclidean n-dim space En
Affine combination:
 1A1 +  2A2 + … +  kAk ,
1 + 2+ … + k = 1
Convex combination:
 1A1 +  2A2 + … +  kAk ,
 1 +  2 + … +  k = 1,
 1 ,…,  k  0
1.3 Affine / Convex Hull
•Affine Hull of a finite set of points A1 ,…, Ak
 1A1 +  2A2 + … +  kAk :
 1 +  2 + … +  k = 1
•Convex Hull of a finite set of points A1 ,…, Ak
 1A1 +  2A2 + … +  kAk :
 1 +  2 + … +  k = 1,  i  0
Affine (Convex) Hull of a set S, notation Aff (S)
(Conv (S)), is the set of all affine (convex)
combinations of finite subsets of S.
Examlpes
• Line AB is the affine hull of A and B.
• Plane ABC is the affine hull of affinely
independent points A, B and C.
• ...
• Segment [A,B]. - is the set of points on AB which
are between A and B, i.e. the set of convex
combinations of A and B.
• Triangle, ...
1.4 Exercises
Exercise 1
Prove that if a point B belongs to the affine
hull Aff (A1, A2, …, Ak ) of points A1, A2,…,
Ak , then:
Aff (A1, A2,…, Ak) = Aff (B,A1, A2,…, Ak).
1.4 Exercises (cont.)
Exercise 2
• Prove that the affine hull Aff (A1, A2, …, Ak ) of
points A1, A2,…, Ak contains the line AB with
each pair of its points A,B.
• Moreover, prove that Aff (A1, A2, …, Ak )
is the smallest set containing {A1, A2, …, A k } and
having this property.
[This property therefore may serve as a
definition of affine sets. ]
(Hint: proof by induction.)
1.4 Exercises (cont.)
Exercise 3
Prove that Aff (A1,, A2, …, Ak ) is independent of the
transformation of coordinates.
Definition: Affine transformation of coordinates:
Matrix multiplication :
Matrix translation:
X -> X• Mnn
X-> X + O’
1.4 Exercises (cont.)
Exercise 1’-3’
Reformulate exercises 1-3 by substituting:
•Aff (A1, A2, …, Ak ) with Conv (A1, A2, …, Ak )
•line AB with segment [A,B].
•Definition: Convex set is a set which contains
the segment [A,B] with each pair of its elements
A and B.
1.4 Exercises (cont.)
Exercise 4
If a convex set S contains the vertices
A1, A2, …, Ak of a polygon P=A1A2…Ak ,
it contains the polygon P.
(Hint: Interior point property).
1.4 Exercises (cont.)
Exercise 5-5’
Prove that Aff (S) (Conv ( S)) is the smallest affine
(convex) set containing S, i. e. the smallest set X which
contains the line AB (segment [AB]) with each pair of points
A, B  X.
Alternatively:
Definition: Convex Hull of a set of points S, notation Conv
(S ) is the smallest convex set containing S.
1.4 Exercises (cont.)
Exercise 6-6’
Prove that:
Aff (A1, A2, …, Ak ) = Aff (A1,, Aff (A2, …, Ak ) ).
Conv (A1, A2, …, Ak ) = Conv (A1,, Conv (A2, …, Ak ) ).
1.4 Exercises (cont.)
Definiton: A set S of points is said to be affinely
(convex) independent if no point of S is an
affine combination of the others.
Affine (convex) basis BS of a set S is an
affinely (convex) independent subset of S
such that every point in S is an affine
(convex) combination of points from BS.
Exercise 7
A set A1, A2,…, Ak is affinely independent if
and only if the set of vectors A1A2,…, A1Ak
is linearly independent.
Therefore...
Every set in En has an affine basis of k  n+1
points. (easy to prove).
It has also a convex basis (not easy to prove),
which is not necessarily finite.
A number of points in an affine basis of a set S
is constant and said to be the dimension of S.
Theorem
If S is a finite set of points, then Conv (S) is
a polygon with the vertices in S.
Proof:
1. There is a convex polygon PS with the
vertices in S. (for example, Algorithm1)
2. PS= Conv (S).