Randomized 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 Backwards analysis • compute expected time to insert Si−1 → Si • backwards: time to delete Si → Si−1 • conditions on Si • but generally analysis doesn’t care what Si is. Trapezoidal decomposition: Motivation: • manipulate/analayze a collection of n segments • assume no degeneracy: endpoints distinct • (simulate touch by slight crossover) • e.g. detect segment intersections • e.g., point location data structure Basic idea: • – Draw verticals at all points and intersects – Divides space into slabs – binary search on x coordinate for slab – binary search on y coordinate inside slab (feasible since lines noncrossing) – problem: Θ(n2) space Definition. 1• draw altitudes from each endpoints and intersection till hit a segment. • trapezoid graph is planar (no crossing edges) • each trapezoid is a face show a face. • • one face may have many vertices (from altitudes that hit the outside of the face) • but max vertex degree is 6 (assuming nondegeneracy) • so total space O(n + k) for k intersections. • number of faces also O(n + k) (at least one edge/face, at most 2 face/edge) • (or use Euler’s theorem: nv − ne + nf ≥ 2) • standard clockwise pointer representation lets you walk around a face Randomized incremental construction: • to insert segment, start at left endpoint • draw altitudes from left end (splits a trapezoid) • traverse segment to right endpoint, adding altitudes whenever intersect • traverse again, erasing (half of) altitudes cut by segment Implementation • clockwise ordering of neighbors allows traversal of a face in time proportional to number of vertices • for each face, keep a (bidirectional) pointer to all not-yet-inserted left-endpoints in face • to insert line, start at face containing left endpoint traverse face to see where leave it • • create intersection, – update face (new altitude splits in half) – update left-end pointers • segment cuts some altititudes: destroy half – removing altitude merges faces – update left-end pointers – (note nonmonotonic growth of data structure) 2� � � � � Analysis: • Overall, update left-end-pointers in faces neighboring new line time to insert s is• (n(f ) + �(f )) f ∈F (s) where – F (s) is faces s bounds after insertion – n(f ) is number of vertices on face f boundary – �(f ) is number of left-ends inside f . • So if Si is first i segments inserted, expected work of insertion i is 1 � (n(f ) + �(f ))i s∈Si f ∈F (s) • Note each f appears at most 4 times in sum since at most 4 lines define each trapezoid. • so O( 1 if (n(f ) + �(f ))). • Bound endpoint contribution: – note �(f ) = n − if – so contributes n/i – so total O(n log n) (tight to sorting lower bound) Bound intersection contribution • – n(f ) is just number of vertices in planar graph – So O(ki + i) if ki intersections between segments so far – so cost is E[ki] – intersection present if both segments in first i insertions – so expected cost is O((i2/n2)k) – so cost contribution (i/n2)k – sum over i, get O(k) – note: adding to RIC, assumption that first i items are random. • Total: O(n log n + k) 3Search structure Starting idea: • extend all vertical lines infinitely • divides space into slabs • binary search to find place in slab • binary search in slab feasible since lines in slab have total order • O(log n) search time Goal: apply binary search in slabs, without n2 space • Idea: trapezoidal decom is “important” part of vertical lines • problem: slab search no longer well defined but we show ok • The structure: A kind of search tree • • “x nodes” test against an altitude • “y nodes” test against a segment • leaves are trapezoids each node has two children • • But may have many parents Inserting an edge contained in a trapezoid • update trapezoids • build a 4-node subtree to replace leaf Inserting an edge that crosses trapezoids • sequence of traps Δi • Say Δ0 has left endpoint, replace leaf with x-node for left endpoint and y-node for new segment Same for last Δ • middle Δ: • – each got a piece cut off 4– cut off piece got merged to adjacent trapezoid – Replace each leaf with a y node for new segment – two children point to appropriate traps – merged trap will have several parents—one from each premerge trap. Search time analysis • depth increases by one for new trapezoids • RIC argument shows depth O(log n) – Fix search point q, build data structure – Length of search path increased on insertion only if trapezoid containing q changes – Odds of top or bottom edge vanishing (backwards analysis) are 1/i – Left side vanishes iff unique segment defines that side and it vanishes – So prob. 1/i – Total O(1/i) for ith insert, so O(log n) overall. Treaps Dictionaries for ordered sets • New Operations. – enumerate in order – successor-of, predecessor-of (even if not in set) – join(S, k, T ), split, paste(S, T ) Binary tree. • child and parent pointers • endogenous: leaf nodes empty. • balanced if depth O(log n) • average case. worst case • Tree balancing • rotations (show) • implementing operations. • red/black, AVL 5• splay trees. – drawbacks in geometry: – auxiliary structure on nodes in subtree (eg, for remaining dimensions) – rebuild on rotation Returning to average case: • Assign random “arrival orders” to keys Build tree as if arrived in that order • • Average case applies No rotations on searches • Choosing priorities • define arrival by random priorities • assume continuous distribution, fix. • eg, use 2 log n bits, w.h.p. no collisions Treaps. • tree has keys in heap order of priorities • unique tree given priorities—follows from insertion order • implement insert/delete etc. • rotations to maintain heap property Depth d(x) analysis • Tree is trace of a quicksort • We proved O(log n) w.h.p. lemma: for x rank k, E[d(x)] = Hk + Hn−k+1 − 1