Geometry Model RAM• • operations on reals, including sqrts. • (why OK) • line segment intersections DISCRETE randomization • Applications: • graphics of course • any domain where few variables, many constraints Point location in line arrangements setup: • n lines in plane • gives O(n2) convex regions • goal: given point, find containing region. • for convenience, use triangulated T (L) • triangulation introduces O(n2) segments (planar graph) • assume all inside a bounding triangle how about a binary space partition? • single line splits input into two groups of n-1 rays • search time (depth) could be n A good algorithm: • choose r random lines R, triangulate • inside each triangle, some lines. • good if each triangle has only an(log r)/r lines in it • will show good with prob. 1/2 • recurse in each triangle—halves lines 1� Lookup method: O(log n) time. Proof of good • As with cut sampling, consider individual “problem” events, show unlikely • Let Δ be all triplets of L-intersections • when δ ∈ Δ is bad: – let I(δ) be number of lines hitting δ – let G(δ) be lines that induce δ (at most 6) – for bad δ, must have all lines of G(δ) in R (call this B1(δ)), no lines of I(δ) in R (call this B2(δ). • bound prob. of bad δ: – we know Pr[δ] ≤ Pr[B1(δ)] Pr[B2(δ) B1(δ)] | (why not equal? Because triangulation may not create triangle from δ) – Given B1(δ), still need r − G(δ) ≥ r − 6 ≥ r/2 drawings (assuming r > 12)| | – prob. none picked is at most (1 −|I(δ)| )r/2 ≤ e−rI(δ)/2n n – Only care if I(δ) > an(log r)/r—large triplets – Pr[B2(δ) | B1(δ)] ≤ r−a/2 for large triplet • prob. some bad at most r−a/2 Pr[B1(δ)] δ • sum is expected number of large triplets. – at most r2 points in sample – at most (r2)3 = r6 triplets in sample – expectation at most r6 – choose a > 12, deduce result. Construction time: Recurrence• T (n) ≤ n 2 2+�(r))+ cr 2T (an log r ) = O(n r • � decreasing with r • by choosing large r, arbitrarily close to O(n2) 2Randomized incremental construction Special sampling idea: • Sample all except one item • hope final addition makes small or no change Method: • process items in order • average case analysis • randomize order to achieve average case • e.g. binary tree for sorting Randomized incremental sorting • Funny implementation of quicksort • repeated insert of item into so-far-sorted • each yet-uninserted item points to “destination interval” in current partition • bidirectional pointers (interval points back to all contained items) • when insert x to I, – splits interval I (x is “pivot” for I) – must update all I-pointers to one of two new intervals – finding items in I easy (since back pointers) – work proportional to size of I • If analyze insertions, bigger intervals more likely to update; lots of quadratic terms. Backwards analysis • run algorithm backwards • at each step, choose random element to un-insert • find expected work works because: • – condition on what first i objects are – which is ith is random – discover didn’t actually matter what first i items are. 3Apply analysis to Sorting: • at step i, delete random of i sorted elements • un-update pointers in adjacent intervals • each pointer has 2/i chance of being un-updated • expected work O(n/i). true whichever are i elements. • • sum over i, get O(n log n) • compare to trouble analyzing insertion – large intervals more likely to get new insertion – for some prefixes, must do n − i updates at step i. Convex Hulls Define • assume no 3 points on straight line. • output: – points and edges on hull – in counterclockwise order – can leave out edges by hacking implementation Ω(n log n) lower bound via sorting algorithm (RIC): • random order pi • insert one at a time (to get Si) • update conv(Si−1) → conv(Si) – new point stretches convex hull – remove new non-hull points – revise hull structure Data structure: • point p0 inside hull (how find? centroid of 3 vertices.) • for each p, edge of conv(Si) hit by �p0p 4• say p cuts this edge • To update pi in conv(Si−1): – if pi inside, discard – delete new non hull vertices and edges – 2 vertices v1, v2 of conv(Si−1) become pi-neighbors – other vertices unchanged. • To implement: – detect changes by moving out from edge cut by �p0p. – for each hull edge deleted, must update cut-pointers to � piv2iv1 or � pRuntime analysis • deletion cost of edges: – charge to creation cost – 2 edges created per step – total work O(n) • pointer update cost – proportional to number of pointers crossing a deleted cut edge – backwards analysis ∗ run backwards ∗ delete random point of Si (not conv(Si)) to get Si−1 ∗ same number of pointers updated ∗ expected number O(n/i) what Pr[update p]? · Pr[delete cut edge of p]· Pr[delete endpoint edge of p]· 2/i· ∗ deduce O(n log n) runtime Book studies 3d convex hull using same idea, time O(n log n), also gets voronoi diagram and Delauney triangulations.