CSC 445/545 – Summer 2021
Points and Polygons
University of Victoria – CSC 445/545 – Summer 2021
1
Bill Bird
Department of Computer Science University of Victoria
June 4, 2021
Designing Linear Programs
We have seen several reasons for preferring linear programs over non-linear ones, but many optimization problems appear to be inherently non-linear.
Designing a linear program to solve an applied problem can be challenging. This lecture covers a few examples of unconventional applications of linear optimization.
University of Victoria – CSC 445/545 – Summer 2021 2
Largest Disk in a Convex Polygon (1)
5.00
4.00
3.00
2.00
1.00
0.00
0.00 2.00 4.00
6.00 8.00
10.00
P1
P2
P3
P0
P4
P5
Consider a convex polygon in the plane on vertices P0, P1, . . . , Pn−1, where the ordering of vertices is guaranteed to be a clockwise traversal in the plane.
University of Victoria – CSC 445/545 – Summer 2021 3
x
y
Largest Disk in a Convex Polygon (2)
5.00
4.00
3.00
2.00
1.00
0.00
0.00 2.00 4.00
6.00 8.00
10.00
P1
P2
P3
P0
P4
P5
(In particular, the ordering ensures that each edge of the polygon is a line segment of the form PiPi+1)
x
University of Victoria – CSC 445/545 – Summer 2021 4
y
Largest Disk in a Convex Polygon (3)
5.00
4.00
3.00
2.00
1.00
0.00
0.00 2.00 4.00
6.00 8.00
10.00
P1
P2
P3
(cx, cy)
r
P0
P4
P5
Task: Find the centre point and radius of the largest disk that can be entirely inscribed in the polygon.
University of Victoria – CSC 445/545 – Summer 2021 5
x
y
Largest Disk in a Convex Polygon (4)
5.00
4.00
3.00
2.00
1.00
0.00
0.00 2.00 4.00
6.00 8.00
10.00
P1
P2
P3
(cx, cy)
r
P0
P4
P5
(This problem is presented in Section 2.6 of the Matouˇsek and G ̈artner book, but in a completely different way)
University of Victoria – CSC 445/545 – Summer 2021 6
x
y
Largest Disk in a Convex Polygon (5)
5.00
4.00
3.00
2.00
1.00
0.00
0.00 2.00 4.00
6.00 8.00
10.00
P2
P1
(cx, cy)
P0
r
P3
P5
P4
Note that the largest disk may not be centred inside the polygon.
University of Victoria – CSC 445/545 – Summer 2021
7
x
y
Largest Disk in a Convex Polygon (6)
5.00
4.00
3.00
2.00
1.00
0.00
0.00 2.00 4.00
6.00 8.00
10.00
P2
P1
(cx, cy)
P0
r
P3
P5
P4
Observation: The largest disk will always touch at least two sides of the polygon, but may not touch all of them.
University of Victoria – CSC 445/545 – Summer 2021 8
x
y
Largest Disk in a Convex Polygon (7)
5.00
4.00
3.00
2.00
1.00
0.00
0.00 2.00 4.00
6.00 8.00
10.00
P1
P2
P3
(cx, cy)
r
P0
P4
P5
Observation: The largest disk will always touch at least two sides of the polygon, but may not touch all of them.
University of Victoria – CSC 445/545 – Summer 2021 9
x
y
Largest Disk in a Convex Polygon (8)
5.00
4.00
3.00
2.00
1.00
0.00
0.00 2.00 4.00
6.00 8.00
10.00
P1
P0
(cx, cy)
r
P2
Observation: The largest disk will always touch at least two sides of the polygon, but may not touch all of them.
University of Victoria – CSC 445/545 – Summer 2021 10
x
y
Largest Disk in a Convex Polygon (9)
5.00
4.00
3.00
2.00
1.00
0.00
0.00 2.00 4.00
6.00 8.00
10.00
P2
P1
(cx, cy)
P0
r
P3
P5
P4
The positions of the vertices are all constant, so the optimization variables are the coordinates (cx , cy ) of the centre point of the disk, and the radius r .
University of Victoria – CSC 445/545 – Summer 2021 11
x
y
Largest Disk in a Convex Polygon (10)
5.00
4.00
3.00
2.00
1.00
0.00
0.00 2.00 4.00
6.00 8.00
10.00
P2
P1
(cx, cy)
P0
P3
P5
P4
Fundamentally, the goal is to find a point (cx,cy) such that the distance from (cx,cy) to the closest edge of the polygon is maximized.
University of Victoria – CSC 445/545 – Summer 2021 12
x
y
Largest Disk in a Convex Polygon (11)
5.00
4.00
3.00
2.00
1.00
0.00
0.00 2.00 4.00
6.00 8.00
10.00
P2
P1
(cx, cy)
P0
P3
P5
P4
Although distance computations normally require square roots, it is possible to avoid the use of a square root in the optimization problem by preprocessing.
University of Victoria – CSC 445/545 – Summer 2021 13
x
y
Largest Disk in a Convex Polygon (12)
For a polygon P0, P1, . . . , Pn−1, let Pn = P0 (as a notational convenience) and define ei =Pi+1−Pi
for i ∈ {0, 1, . . . , n − 1}.
University of Victoria – CSC 445/545 – Summer 2021
14
Largest Disk in a Convex Polygon (13)
5.00
4.00
3.00
2.00
1.00
0.00
0.00 2.00 4.00
6.00 8.00
10.00
P2
P1
e1
e2
e0 P0
e5
P3
P5
e4
e3
P4
Each vector ei is parallel to the edge PiPi+1 of the polygon.
University of Victoria – CSC 445/545 – Summer 2021
15
x
y
Largest Disk in a Convex Polygon (14)
Now, define
vi = (−eiy,eix).
Each vector vi is orthogonal to the corresponding ei (and therefore, vi is a normal vector to the edge PiPi+1). Additionally, due to the requirement that the vertices of the polygon were provided in clockwise order, vi will always be an outward-pointing normal vector.
Finally, let
vv ii
ni= = . ||vi|| v2 +v2 ix iy
Computing ni requires a square root, but since ni depends only on the (constant) input points, it can be precomputed (before any LP is constructed).
University of Victoria – CSC 445/545 – Summer 2021 16
Largest Disk in a Convex Polygon (15)
5.00
4.00
3.00
2.00
1.00
0.00
0.00 2.00 4.00
6.00 8.00
10.00
P2 n1
P1
n2
n0
P0
P3
n5
P5
n4
P4
n3
x
Each vector ni is an outward-pointing unit normal vector for the edge PiPi+1.
University of Victoria – CSC 445/545 – Summer 2021 17
y
Largest Disk in a Convex Polygon (16)
5.00
4.00
3.00
2.00
1.00
0.00
0.00 2.00 4.00
6.00 8.00
10.00
P1
P0
(cx, cy)
Q
n2
P2
The points Q on the line PiPi+1 must have
Q·ni =Pi·ni =Pi+1·ni.
University of Victoria – CSC 445/545 – Summer 2021
18
x
y
Largest Disk in a Convex Polygon (17)
5.00
4.00
3.00
2.00
1.00
0.00
0.00 2.00 4.00
6.00 8.00
10.00
P1
P0
(cx, cy)
Q
n2
P2
Additionally, any point R inside the polygon must have R · ni ≤ Pi · ni
for all i ∈ {0, 1, . . . , n − 1}. University of Victoria – CSC 445/545 – Summer 2021
19
x
y
Largest Disk in a Convex Polygon (18)
5.00
4.00
3.00
2.00
1.00
0.00
0.00 2.00 4.00
6.00 8.00
10.00
P1
P0
(cx, cy)
Q
n2
P2
Any point of the form Q = C + d ni will have Euclidean distance d from the point C (since ||ni || = 1).
University of Victoria – CSC 445/545 – Summer 2021 20
x
y
Largest Disk in a Convex Polygon (19)
5.00
4.00
3.00
2.00
1.00
0.00
0.00 2.00 4.00
6.00 8.00
10.00
P1
P0
(cx, cy)
Q
n2
P2
The closest point to C = (cx,cy) on the edge PiPi+1 will always have the form Q = C + dni .
University of Victoria – CSC 445/545 – Summer 2021
21
x
y
Largest Disk in a Convex Polygon (20)
We can combine these observations to construct constraints for a linear program.
A disk of radius r centred at C = (cx , cy ) is completely contained in the polygon if, for
i ∈{0,1,…,n−1},
Rearranging terms gives the inequality
which can be simplified to
C · ni + r ≤ Pi · ni .
Removing the vector notation gives
cxnix +cyniy +r ≤Pixnix +Piyniy,
which is linear.
University of Victoria – CSC 445/545 – Summer 2021
22
(C+rni)·ni ≤Pi ·ni. C·ni +rni ·ni ≤Pi ·ni
Largest Disk in a Convex Polygon (21)
The goal of the largest disk problem is to find values cx,cy and r, with the maximum possible radius r , such that the entire disk of radius r around (cx , cy ) is contained in the polygon.
This can be achieved with the following linear program over cx , cy and r
max. r
s.t. cxnix +cyniy +r ≤ Pixnix +Piyniy fori∈{0,1,…,n−1}
r≥0
There are a total of n constraints. Note that the right hand side of each constraint is a constant (and can be precomputed before solving the LP). The values of nix and niy are also constants.
University of Victoria – CSC 445/545 – Summer 2021 23
Linear Classifiers (1)
5.00
4.00
3.00
2.00
1.00
0.00
0.00 2.00 4.00
6.00 8.00
10.00
Consider a dataset consisting of two sets of points: Set A (blue, round) and Set B (red, square).
University of Victoria – CSC 445/545 – Summer 2021 24
x
y
Linear Classifiers (2)
5.00
4.00
3.00
2.00
1.00
0.00
0.00 2.00 4.00
6.00 8.00
10.00
Task: Determine if there exists a single line that separates every point in Set A from every point in Set B.
University of Victoria – CSC 445/545 – Summer 2021 25
x
y
Linear Classifiers (3)
5.00
4.00
3.00
2.00
1.00
0.00
0.00 2.00 4.00
6.00 8.00
10.00
(This problem is presented in Section 2.5 of the Matouˇsek and G ̈artner book, but the solution there relies on a simplification that could be problematic, so it is recommended not to rely on the version in that book)
University of Victoria – CSC 445/545 – Summer 2021 26
x
y
Linear Classifiers (4)
5.00
4.00
3.00
2.00
1.00
0.00
0.00 2.00 4.00
6.00 8.00
10.00
(This problem is also presented in Section 12.7 of the Vanderbei book, which does use the more correct general solution used here, although stated differently)
University of Victoria – CSC 445/545 – Summer 2021 27
x
y
Linear Classifiers (5)
5.00
4.00
3.00
2.00
1.00
0.00
0.00 2.00 4.00
6.00 8.00
10.00
For visual convenience, this example will use points in 2d, but the same techniques apply for any number of dimensions.
University of Victoria – CSC 445/545 – Summer 2021 28
x
y
Linear Classifiers (6)
5.00
4.00
3.00
2.00
1.00
0.00
0.00 2.00 4.00
6.00 8.00
10.00
In three dimensions, the task is to find a separating plane. In n dimensions, the task is to find a separating hyperplane.
University of Victoria – CSC 445/545 – Summer 2021 29
x
y
Linear Classifiers (7)
5.00
4.00
3.00
2.00
1.00
0.00
0.00 2.00 4.00
6.00 8.00
10.00
The construction of linear classifiers like these is important in Machine Learning applica- tions.
University of Victoria – CSC 445/545 – Summer 2021 30
x
y
Linear Classifiers (8)
As usual, we can characterize the desired separator line in terms of a normal vector c. In particular, we want a vector c ∈ Rn and a value d ∈ R such that
c · P < d for P ∈ A c · P > d for P ∈ B
Note that strict inequalities (< and >) are not permitted in linear programs (since a linear constraint with a strict inequality defines a half space without a closed boundary).
University of Victoria – CSC 445/545 – Summer 2021 31
Linear Classifiers (9)
First try: If we relax the strict inequalities, we can produce m = |A| + |B| constraints of the form
c · P ≤ d for P ∈ A c · P ≥ d for P ∈ B
and construct a linear program with a trivial objective function to find the values of c and d.
min. 1
s.t. c1p1+c2p2+…+cnpn ≤ d for(p1,p2,…,pn)∈A
c1p1+c2p2+…+cnpn ≥ d for(p1,p2,…,pn)∈B (In an LP with a constant objective function, any feasible solution is optimal)
University of Victoria – CSC 445/545 – Summer 2021 32
Linear Classifiers (10)
5.00
4.00
3.00
2.00
1.00
0.00
0.00 2.00 4.00
6.00 8.00
10.00
Due to the absence of strict inequalities, it is possible for the solution to be a line which is incident to one of the input points. This is undesirable, since we want each point to lie strictly on one side of the line.
University of Victoria – CSC 445/545 – Summer 2021 33
x
y
Linear Classifiers (11)
5.00
4.00
3.00
2.00
1.00
0.00
0.00 2.00 4.00
6.00 8.00
10.00
Even if the LP yields a line that lies strictly between the two sets of points, there are many possible solutions and no guarantee that the chosen solution will have any particular properties (besides obeying the constraints).
University of Victoria – CSC 445/545 – Summer 2021 34
x
y
Linear Classifiers (12)
5.00
4.00
3.00
2.00
1.00
0.00
0.00 2.00 4.00
6.00 8.00
10.00
(On the other hand, if the LP is infeasible, then no separating plane exists)
University of Victoria – CSC 445/545 – Summer 2021
35
x
y
Linear Classifiers (13)
5.00
4.00
3.00
2.00
1.00
0.00
0.00 2.00 4.00
6.00 8.00
10.00
Among the possible solutions, the ideal solution is the line that maximizes the distance to the nearest point in either set.
University of Victoria – CSC 445/545 – Summer 2021 36
x
y
Linear Classifiers (14)
Second try: We can introduce a variable q ≥ 0 which represents a ‘buffer’ between the two sets, then try to maximize q:
max. q
s.t. c1p1 + c2p2 + . . . + cnpn ≤ d − q for (p1, p2, . . . , pn) ∈ A
c1p1+c2p2+…+cnpn ≥ d+q for(p1,p2,…,pn)∈B q≥0
In this formulation, if the LP is infeasible or the optimal value of q is equal to zero, no separating plane exists.
University of Victoria – CSC 445/545 – Summer 2021 37
Linear Classifiers (15)
max. q
s.t. c1p1 + c2p2 + . . . + cnpn ≤ d − q for (p1, p2, . . . , pn) ∈ A
c1p1+c2p2+…+cnpn ≥ d+q for(p1,p2,…,pn)∈B q≥0
The LP formulation above is not yet correct, and will be unbounded in cases where a separating plane exists.
Specifically, if c1,c2,…,cn,d,q is a feasible solution, so is sc1,sc2,…,scn,sd,sq, so if a feasible solution exists, the value of q can be made arbitrarily large.
University of Victoria – CSC 445/545 – Summer 2021 38
Linear Classifiers (16)
Third try: To prevent arbitrarily scaling feasible solutions, restrictions can be placed on the magnitude of some of the variables. It is important to justify the restrictions (to prevent artificially limiting the solution space).
Notice that if then
c · P ≤ d − q, c·P≤d−q.
||c || ||c ||
Therefore, the choice of c can be restricted to unit vectors only (or to vectors whose
magnitude is bounded by some constant).
University of Victoria – CSC 445/545 – Summer 2021 39
Linear Classifiers (17)
Enforcing a constraint like
||c||=c12 +c2 +…+cn2 ≤1
is not possible in an LP, but it is possible to restrict each ci to the range [−1, 1], which is a weaker restriction than requiring a unit vector (but still sufficient to prevent arbitrary scaling).
It is also possible to use the constraint ||c||2 = c12 + c2 + . . . + cn2 ≤ 1 (which is equivalent to ||c|| ≤ 1), which may produce a more accurate result, but will also require quadratic programming since the constraint is not linear.
University of Victoria – CSC 445/545 – Summer 2021 40
Linear Classifiers (18)
The resulting LP is
max. q
s.t. c1p1 + c2p2 + . . . + cnpn ≤ d − q for (p1, p2, . . . , pn) ∈ A
c1p1+c2p2+…+cnpn ≥ d+q for(p1,p2,…,pn)∈B q≥0
−1≤ci ≤ 1
University of Victoria – CSC 445/545 – Summer 2021
41
Linear Classifiers (19)
5.00
4.00
3.00
2.00
1.00
0.00
0.00 2.00 4.00
6.00 8.00
10.00
In cases where a separating plane exists, the final LP will always produce a line with the maximum margin between each point set.
University of Victoria – CSC 445/545 – Summer 2021 42
x
y
Linear Classifiers (20)
5.00
4.00
3.00
2.00
1.00
0.00
0.00 2.00 4.00
6.00 8.00
10.00
In cases where a separating plane exists, the final LP will always produce a line with the maximum margin between each point set.
University of Victoria – CSC 445/545 – Summer 2021 43
x
y
Linear Classifiers (21)
5.00
4.00
3.00
2.00
1.00
0.00
0.00 2.00 4.00
6.00 8.00
10.00
In cases where a separating plane exists, the final LP will always produce a line with the maximum margin between each point set.
University of Victoria – CSC 445/545 – Summer 2021 44
x
y
Linear Classifiers (22)
5.00
4.00
3.00
2.00
1.00
0.00
0.00 2.00 4.00
6.00 8.00
10.00
The term support vector comes from the fact that the line is determined only by the closest points in each point set. The other points have no bearing on the result.
University of Victoria – CSC 445/545 – Summer 2021 45
x
y
Non-Linear Classifiers (1)
The LP to find a linear classifier in two dimensions uses optimization to find coefficients cx and cy such that the equation
cx x + cy y
has a particular result on a specified set of (fixed) (x,y) pairs (namely, the points in the
sets A and B).
It turns out that the same logic can be used to design LPs to find non-linear classifiers.
University of Victoria – CSC 445/545 – Summer 2021 46
Non-Linear Classifiers (2)
5.00
4.00
3.00
2.00
1.00
0.00
0.00 2.00 4.00
6.00 8.00
10.00
For example, there is no separating plane for the sets of points above.
University of Victoria – CSC 445/545 – Summer 2021
47
x
y
Non-Linear Classifiers (3)
5.00
4.00
3.00
2.00
1.00
0.00
0.00 2.00 4.00
6.00 8.00
10.00
For example, there is no separating plane for the sets of points above.
University of Victoria – CSC 445/545 – Summer 2021
48
x
y
Non-Linear Classifiers (4)
5.00
4.00
3.00
2.00
1.00
0.00
0.00 2.00 4.00
6.00 8.00
10.00
y
However, there is a quadratic function (of x and y) that can separate the two sets.
University of Victoria – CSC 445/545 – Summer 2021 49
x
Non-Linear Classifiers (5)
Fundamentally, the LP for linear classification was a tool for finding a function f(x,y) and parameters d and q such that
f(x,y)≤d−q forP∈A f(x,y)≥d+q forP∈B
with the choice of f(x,y) restricted to a function of the form cxx +cyy (that is, a linear function).
University of Victoria – CSC 445/545 – Summer 2021 50
Non-Linear Classifiers (6)
Consider a quadratic function of the form
f (x , y ) = ax 2 + by 2 + rxy + sx + ty + c
with 6 coefficients (a, b, r, s, t and c). As in the case of a linear classifier, the values of x and y are provided by points from the input sets A and B (and are therefore not the subject of optimization).
Therefore, it is possible to construct an LP over a,b,r,s,t,c,d and q to find the largest margin q such that
f(x,y)≤d−q forP∈A f(x,y)≥d+q forP∈B
since in terms of the optimization variables, the function f(x,y) is linear.
(As in the linear case, the coefficients a, b, r, s, t and c must be restricted to the range
[−1, 1] to prevent arbitrary scaling)
University of Victoria – CSC 445/545 – Summer 2021 51
Non-Linear Classifiers (7)
5.00
4.00
3.00
2.00
1.00
0.00
0.00 2.00 4.00
6.00 8.00
10.00
For this point set, the points in Set A (blue) are grouped in an approximately elliptical region surrounded on all sides by Set B (red). Note that an ellipse can be characterized by a quadratic equation.
University of Victoria – CSC 445/545 – Summer 2021 52
x
y
Non-Linear Classifiers (8)
5.00
4.00
3.00
2.00
1.00
0.00
0.00 2.00 4.00
6.00 8.00
10.00
y
The solution to the linear program yields the function f(x,y) above, along with a threshold value d and a margin q.
University of Victoria – CSC 445/545 – Summer 2021 53
x
Non-Linear Classifiers (9)
5.00
4.00
3.00
2.00
1.00
0.00
0.00 2.00
Thecurvef(x,y)=d isshownabove.
4.00
6.00 8.00
10.00
University of Victoria – CSC 445/545 – Summer 2021
54
x
y
Non-Linear Classifiers (10)
5.00
4.00
3.00
2.00
1.00
0.00
0.00 2.00 4.00
6.00 8.00
10.00
y
All of the points in Set A have f(x,y) ≤ d −q, and all of the points in Set B have f (x, y) ≥ d + q.
University of Victoria – CSC 445/545 – Summer 2021 55
x
Non-Linear Classifiers (11)
5.00
4.00
3.00
2.00
1.00
0.00
0.00 2.00 4.00
6.00 8.00
10.00
y
Due to the larger number of coefficients, a much greater variety of classifier shapes can be modeled.
University of Victoria – CSC 445/545 – Summer 2021 56
x
Non-Linear Classifiers (12)
5.00
4.00
3.00
2.00
1.00
0.00
0.00 2.00 4.00
6.00 8.00
10.00
y
Specifically, the curve defined by the classifier can be any conic section (circle, ellipse, hyperbola or parabola).
University of Victoria – CSC 445/545 – Summer 2021 57
x
Non-Linear Classifiers (13)
5.00
4.00
3.00
2.00
1.00
0.00
0.00 2.00 4.00
6.00 8.00
10.00
y
Specifically, the curve defined by the classifier can be any conic section (circle, ellipse, hyperbola or parabola).
University of Victoria – CSC 445/545 – Summer 2021 58
x