Unformatted text preview:

6.854 Advanced AlgorithmsLecture 25: 11/12/2004 Lecturer: David KargerScribes: Charles HanRandomized Incremental Construction II25.1 Convex HullThe following algorithm provides a randomized incremental construction for convex hull: start with3 points, then process the remaining points in random order, updating the convex hull each time .Define the set Sito the first i points processed, and define conv(Si) to be the convex hull of Si.Throughout the algorithm, we want to maintain the vertices and edges of conv(Si) We take somepoint p0that lies inside conv(Si), and notice the following about the remaining points p: if thehalf-line−→p0p cuts any segment of conv(Si), then that segment will leave conv(Si) if p is added to thehull. It is also useful to observe that for each non-hull point p, there is exactly one edge that is cutby−→p0p. We also know that So, when adding some point pi, we know that the convex hull changesif−→p0p cuts a segment before reaching p. If we know that the hull changes, do the following: startat the cut segment, then walk clockwise, removing all absorbed segments until we are done; do thesame going counterclockwise. The total time of this operation is O(1) per removed segment, plusO(1) to add the two new segments connecting pito the convex hull.To be able to know in O(1) time whether a segment was cut or not, we need to maintain a conflictlist for each segment of the current hull; the conflict list maintains pointers to all the vertices (thathave not yet be en added to the hull) that would cut the given segment if added. Given a vertex p,we can easily tell if it cuts a given segment by looking for it in that segment’s conflict list (in O(1)time with hashing, for instance). To build the conflict list for the two new segments after a hullupdate, we need O(1) units of time for each vertex that had a cut segment absorbed by the newsegment.In order for a segment to be deleted, it must have been added at some point, so we can simply chargethe deletion cost to the addition, for a real cost of at most 2 per point; it follows that the cost ofdeletion is O(n). The cost of updating the conflict lists turns out to b e harder to analyze, since thecost depends on the exp e cted number of points in the deleted conflict lists. For this analysis, weturn to the method of backwards analysis.25.2 Backwards AnalysisIn backwards analysis, we simply imagine running our algorithm backwards and count the resultingpointer updates. In this case, we want to know how much work needs to be done whenever weremove a point pifrom Si(not conv(Si)!) to arrive at Si−1. In particular, we are interested in25-1Lecture 25: 11/12/2004 25-2analyzing the total amount of work done on the conflict lists in our convex hull representation. Forthe ith step of the convex hull [de]construction, consider the following:• a given segment of conv(Si) will not change unless it is removed from the convex hull.• if a segment of is removed from the conv(Si), we must remove all of the pointers in its conflictlist.• a segment will only be removed if one of its endpoints is pi.• since each of the i remaining vertices is equally to be removed, each segment in conv(Si) hasa 2/i probability of being removed.Knowing thes e things, we can find the expected number of conflict pointers updated per step:E[# of pointers updated] =Xe∈conv( Si)( [size of e’s conflict list] · [Pr (e is removed)] )=Xe∈conv( Si)[size of e’s conflict list]· ([Pr (e is removed)])= O(n) · ([Pr (e is removed)])= O(n/i)Finally, we can find the total expected amount of work spent maintaining conflict lists over theentire course of the algorithm:E[total exp ecte d work] =nXi=1O(n/i) = O nnXi(1/i)!= O(n log n)25.3 Linear ProgrammingNow consider the following application of randomized incremental construction to linear program-ming. Let d represent the number of variables in our n-constraint linear program. Recall that an LPcan be represented geome trically as the problem of finding the optimal vertex (as measured by theobjective function) in the intersection of d-dimensional half-spaces represented by the constraints.Say that we build our polyhedron by adding our half-spaces in random order, and at each stepmaintaining the current optimum vertex OP T . In order to accurately and efficiently maintain thecurrent OP T , we rely on the following obervation: adding a new constraint will not improve ourcurrent O P T , but it may make it infeasible. To state it a bit differently:Claim 1 Let OP Tibe the optimum vertex of the polyhedron after inserting i constraints (half-spaces). Now add the next constraint ci+1; if OP T(i + 1) 6= OP Ti, then the new optimum vertexOP Ti+1must be tight for the new constraint ci+1Lecture 25: 11/12/2004 25-3Proof: We prove the above claim by contrapo sition. Suppose that ci+1is not tight for OP Ti+1.Then removing ci+1would have no effect on the optimum, implying that OP Ti= OP Ti+1. Thiscontradicts the condition that O P Ti6= OP Ti+1; therefore, the claim holds.We already know the set C of constraints for which the previous OP T was tight, so we can reduceour search for the new OP T to just those contstraints. We also know that the new OP T is tight forour new constraint, so it sufficient to optimize within the hyperplane defined by that constraint. Inthis new optimization problem, we intersect each constraint Cj∈ C with the new tight constraint, andwe also project the objective function onto the new constraint. This gives us a new (d −1)-dimensionoptimization problem, which we can recursively solve in the same manner to find the new OP T .In the worst-case scenario, we would need to recurse for every single new constraint added. Thisbehavior is modelled by the recurrence:T (n, d) = T (1, d − 1) + T (2, d − 1) + ... + T (n, d − 1) ≈ nT (n, d − 1) ≈ ndSince this is a randomized construction, we can hope to do better in the expected case. We onlyneed to recurse in cases where OP Tiis infeasible for constraint ci+1(otherwise, OP Ti= OP Ti+1).At step i in the construction, consider that only d constraints ever specify OP Ti. In a backwardsanalysis, consider removing a random constraint from the polyhedron at step i; we will remove atight constraint only with probability d/i, knowing this, we get a much better-looking recurrence forour algorithm:T (n, d) = T (n − 1, d) + O(n) +dn(T (n − 1, d − 1))This gives an expected running time of O(d!n). This is a strongly polynomial


View Full Document

MIT 6 854 - Randomized Incremental Construction

Download Randomized Incremental Construction
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Randomized Incremental Construction and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Randomized Incremental Construction 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?