Linear Programs

Question 1

What is Linear Programming?

What does it consist of?

Answer 1

Linear Program is an optimization problem.

It consists of:

• A set of decision variables
• A set of linear constraints on the variables
  
  • These are inequalities involving the variables, which only appear with exponent 1
• An objecttive function to optimize (max or min)
  
  • This is any function involving the variables

Question 2

Define the following from the problem below:

1. Decision variables
2. Objective function
3. Constraints

Answer 2

Question 3

What is the definition of the half-plane intersection problem?

Answer 3

Finding the intersection of a given set of half-planes

Definition: Given a set H consisting of n half-planes (eg. linear equalities), computer the intersection.

• In other words, compute the set of points that are in every half-plane in H.

Question 4

The intersection of half-planes is a convex polygon.

What is the definition of convex and convex polygon?

Answer 4

Question 5

What is the observation for Case 1 of an intersection of a Convex Polygon with a Half-Plane.

Draw a diagram

Answer 5

Question 6

What is the observation for Case 2 of an intersection of a Convex Polygon with a Half-Plane.

Draw a diagram

Answer 6

Important to note:

• Half-plane h intersects the boundary of P in at most 2 points
• Can find the intersection points by testing each edge of P, takes Theta(E) time, where E is the # of edges in P
• Once the intersection points x,y are found, can construct P’ by start with x,y,(the intersection points) then adding vertices clockwise untiil we get back to x. Takes Theta(E) time.

Question 7

What is the brute-force solution for Half-Plane Intersection problem.

What is the run time?

Answer 7

Question 8

What is the divide for Half-plane intersection problem?

Input: a set H of n half-planes

Answer 8

Divide: Partition the set H into two sets H₁ and H₂ with equal size n/2

Question 9

What is the conquer for Half-plane intersection problem?

Input: a set H of n half-planes

Answer 9

Conquer: Recursively compute the intersection of each set H₁ and H₂. This will return two convex polygons P₁ and P₂.

Question 10

What is the Combine for Half-plane intersection problem?

Input: a set H of n half-planes

Answer 10

Combine: Compute the intersection of polygons P₁ and P₂

Question 11

in the combine portion of the half-plane problem divide-and-conquer algo

p is an edge in P

q is an edge in Q

What does it mean to advance p or q?

What does it mean if we advance p or q?

Answer 11

Question 12

cases: (red edge = p, blue edge = q)

Given this picture:

Are the edges pointing:

• towards each other,
• away from each other
• p towards q
• q towards p

Which edge should be advanced?

Answer 12

Question 13

cases: (red edge = p, blue edge = q)

Given this picture:

Are the edges pointing:

towards each other,

away from each other

p towards q

q towards p

Which edge should be advanced?

Answer 13

Question 14

cases: (red edge = p, blue edge = q)

Given this picture:

Are the edges pointing:

towards each other,

away from each other

p towards q

q towards p

Which edge should be advanced?

Answer 14

Question 15

cases: (red edge = p, blue edge = q)

Given this picture:

Are the edges pointing:

towards each other,

away from each other

p towards q

q towards p

Which edge should be advanced?

Answer 15

Question 16

In our polygon algorithm, how many times do we traverse each polygon at most?

What does that mean for total steps here?

Answer 16

At most twice,

so 2(E_p+E_q)

Question 17

What is the cost of each step of checking if the two polygons intersect?

Answer 17

O(1) time

Question 18

What is the worst case and actual cost of our comining polygons algo?

Answer 18

Question 19

What is the recurrence relation for the half-plan intersection problem?

Use the master theorem to determine the run time, what case does it fall under?

Answer 19