Linear Programs Flashcards
What is Linear Programming?
What does it consist of?
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
Define the following from the problem below:
- Decision variables
- Objective function
- Constraints
What is the definition of the half-plane intersection problem?
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.
The intersection of half-planes is a convex polygon.
What is the definition of convex and convex polygon?
What is the observation for Case 1 of an intersection of a Convex Polygon with a Half-Plane.
Draw a diagram
What is the observation for Case 2 of an intersection of a Convex Polygon with a Half-Plane.
Draw a diagram
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.
What is the brute-force solution for Half-Plane Intersection problem.
What is the run time?
What is the divide for Half-plane intersection problem?
Input: a set H of n half-planes
Divide: Partition the set H into two sets H1 and H2 with equal size n/2
What is the conquer for Half-plane intersection problem?
Input: a set H of n half-planes
Conquer: Recursively compute the intersection of each set H1 and H2. This will return two convex polygons P1 and P2.
What is the Combine for Half-plane intersection problem?
Input: a set H of n half-planes
Combine: Compute the intersection of polygons P1 and P2
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?
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?
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?
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?
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?
In our polygon algorithm, how many times do we traverse each polygon at most?
What does that mean for total steps here?
At most twice,
so 2(Ep+Eq)
What is the cost of each step of checking if the two polygons intersect?
O(1) time
What is the worst case and actual cost of our comining polygons algo?
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?
