Computational Geometry Lecture Notes and Randomized Linear Programming Overview

Lecture Notes for Introduction to Computational Geometry (Com S 418/518) Yan-Bin Jia, Iowa State University Randomized Linear Programming Point Outline: I. Generation of a random permutation II. Backward analysis of running time III. Unbounded linear program Textbook: Computational Geometry: Algorithms and Applications (3rd ed.) by M. de Berg et al., Springer-Verlag, 2008.

How to Avoid Worst Case? Pick a random ordering of the set ? of half-planes. ? 1 ? 2 Bad order still leads to ?(?2). 6 5 4 ?? 3 Most orders lead to a faster algorithm. ?6 ?5 ?4 ?3 ?2

Algorithm Modification 1, 2 certificate half-planes ?2 ?1 ?2 generate a random permutation of 3, 4, , ? for ? 3 to ? do if ?? 1 ? then ?? ?? 1 else ?? point ? on ?? that maximizes ? subject to 1, 2, , ? 1 if ? does not exist then LP is infeasible return ??

I. Random Permutation Array ?[1..?] 1 ? ? ? for ? ? down to 2 do ? RANDOM(?) ?[?] // returns a random integer between //1 and ? under uniform distribution. ?[?] ?(?)

How Does It Work? 4 RANDOM 4 = 2 3 1 2 RANDOM 3 =1 1 4 2 3 RANDOM 2 = 2 3 4 2 1 Every permutation is equally likely to be generated. 4 2 3 1 Why?

II. Run Time Analysis The LP algorithm is randomized. Its running time depends on random choices. How to analyze the running time? ? 2 ! permutations of 3, 4, , ? Average over all of them (expected time).

Start of Analysis if UNBOUNDEDLP reports that LP is infeasible then return // does not detect all infeasible scenarios else if LP is unbounded // to be discussed then return a ray along which it is unbounded else 1, 2 certificate half-planes ?2 ?1 ?2 generate a random permutation of 3, 4, , ? for ? 3 to ? do if ?? 1 ? then ?? ?? 1 else ?? point ? on ?? that maximizes ? subject to 1, 2, , ? 1 if ? does not exist then LP is infeasible return ?? UNBOUNDEDLP takes time ?(?) to be shown. Random permutation takes time ?(?). Add a half-plane. ?(1) if the optimal vertex does not change. ?(?) for solving a 1D LP otherwise. Bounding the average time for solving all 1D LPs.

Random Variable For stage ? 3 5 4 0 if ?? 1 ? ?4= ?5 1 ??= 2 3 5 6 4 1 otherwise ?6 ?6 ?5 1 2

Expected Time Total time over all half-planes 3, 4, , ?. ? ?(?) ?? ?=3 Expected total time: How to determine? ? ? ? ? ? ?? = ? ? ?(??) ?=3 ?=3 Probability that ?? 1 ? Are we going to exhaust all (topologically) different scenarios of half-plane additions and then assign each a possibility? Too complicated even if possible!

Backward Analysis Look at the algorithm backwards. Assume it has finished with the optimal vertex ?? found. ??is a vertex of ??= ?=1 ? ? ?? 1is from ??after removing ?. Suppose that the optimal point changes at stage ?. ?defines ?? ? a random element of { 1, 2, , ?} Pr{ ?is one of ?? s only two defining half-planes} 2 ? ? ?? ?

2 ? ? Why > 2 half-planes may have boundary lines through ??. ??already existed before addition of ?. (?? 1 ?? and ?? 1 ?) ? ? removal of ? does not affect the vertex. ?

Stage ? To bound ? ??, we fix the set ?? of first ? half-planes. Think one step backward. Pr(computing a new optimal vertex when adding ?) = Pr(the optimal vertex changes when removing a half-plane from ??) 2 ? Thus, ?(??) 2 ?

Expected Running Time for solving an LP is ? ? ?(?) 2 2? ? = ? ? ?=3 ?=3 = ?(?) Theorem 2D linear programming with ? constraints is solvable in ?(?) expected time and ?(?) storage.

III. Unbounded Linear Program UNBOUNDEDLP(?,?) yields a ray ? = ? if LP is unbounded 1, 2 ? such that ({ 1, 2},?) is bounded, otherwise. certificate half-plane ??: outward normal ?? ? ?? [0,?] ?? ?? ?

Minimum Angle ??= min 1 ? ??? ? ?? ? ?

Initial Slab ????= { ? ? | ??= ??} ????= { ? ? | ??= ??} ? ? Parallel boundary lines. ? Compute ???? ? = (???? ????) ???? ?(?) time ? = LP infeasible!

Non-Empty Slab (? ) ? bounded by some line ?? with ? ????. Assumption At least one half-plane not in ???? or ????. Ray ??= ?? ? where 1 ? ?, ? ???? ???? ? ?? ? ?? ?

Case 1: Unbounded LP ??= ?? ? unbounded in ? for all 1 ? ?, ? ???? ????. All ?? lie on ??. ?? is a ray unbounded in ?. ? ???? ???? ? ???? ???? Ray intersection in ?(?) time. ?? ? ???? ???? ?? Lemma 1 If ??= ?? ? is unbounded in ? for every ? ???? ????, then ?,? is unbounded along a ray contained in ?? which can be computed in ? ? time. ? ??

Case 2: Bounded LP Boundary line ?? with ? ???? bounds ?. Lemma 2 If ??= ?? ? is bounded in ? for some ? ???? ????, 1 ? ?, then LP ?, ?,? is bounded. Proof By contradiction. Assume that LP ?, ?,? is unbounded. ?? ? ?? ?? bounded in ? ?? ? = ?? ? must be unbounded. ?? ? ? ? ? ? must be in the region ? between ?? and ? (? ? &? ?) that is contained in ?. ?? ? ??

Contradiction to Choice of ? ? in the region between ? and ??. rotate each vector counterclockwise by ? ?, ? , ?? becomes ??, ?, ??, respectively. 2. ?? must be in the region between ? and ?? (note ?? ??). ?? ? ?? ??< ??= min 1 ? ??? Contradiction! ?? ? ?? ?? ?? ? ? ?? ? ?? ?? ? ? (? ? & ? ?) ? ?? ?? ?

UNBOUNDEDLP(?, ?) Compute??for all 1 ? ? Choose ? such that??= min 1 ? ??? ???? { ? ? | ??= ??} ???? { ? ? | ??= ??} ? ? (???? ????) ? (???? ????) if ? = then LP(?,?) is infeasible else ? ????that bounds ? if ??= ?? ?bounded for some ? ? then LP(?,?) is bounded // it may still be infeasible else LP(?,?) is unbounded along the ray ?? ( ?)

Correctness and Running Time Lemma 3 UNBOUNDEDLP(?, ?) decides whether a 2D LP with ? constrains is unbounded in ?(?) time, and if so, returns a ray in the feasible region unbounded in ?.