1Geometry Field: • We have been doing geometry—eg linear programming • But in computational geometry, key difference in focus: low dimension d • Lots of algorithms that are great for d small, but exponential in d 1.1 Range Trees for Orthogonal Range Queries One key idea in CG: reducing dimension • Do some work that reduces problem to smaller dimension • Since few dimensions, work doesn’t add up much. What points are in this box? • goal: O(n)space • query time O(log n)plus numberofpoints • (can’t beat log n even for 1d) • 1d solution: binary tree. – Find leftmost in range – Walk tree till rightmost Generalize: Solve in each coordinate “separately” • Idea 1: solve each coord, intersecting – Too expensive: maybe large solution in each coord, none in intersec-tion • Idea: – we know x query will be an interval, – so build a y-range structure on each distinct subrange of points by x – Use binary search to locate right x interval – Than solve 1d range search on y – Problem: n2 distinct intervals – So n3 space and time to build Refine idea: • Build binary search tree on x coords 1• Each internal node represents an interval containing some points • Our query’s x interval can be broken into O(log n)tree intervals • We want to reduce dimension: on each subinterval, range search y coords only amound nodes in that x interval • Solution: each internal node has a y-coord search tree on points in its subtree • Size: O(n log n), since each point in O(log n) internal nodes • Query time: find O(log n) nodes, range search in each y-tree, so O(log2 n) (plus output size) • more generally, O(logd n) • fractional cascading improves to O(log n) Dynamic maintenance: • Want to insert/delete points • Problem to maintain tree balance • When insert x coord, may want to rebalance • Rotations are obious choice, but have to rebuild auxiliary structures • Linear cost to rotate a tree. • Remember treaps? – We showed expect 1 rotation – Can show expected size of rotated tree is small – Then insert y coord in O(log n) auxiliary structures – So, O(log2 n) update cost 2 Sweep Algorithms Another key idea: • dimension is low, • so worth expending lots of energy to reduce dimension • plane sweep is a general-purpose dimension reduction • Run a plane/line across space • Study only what happens on the frontier • Need to keep track of “events” that occur as sweep line across • simplest case, events occur when line hits a feature 22.1 Convex Hull by Sweep Line • define • good for: width, diameter, filtering • 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 Build upper hull: • Sort points by x coord • Sweep line from left to right • maintain upper hull “so far” • as encounter next point, check if hull turns right or left to it • if right, fine • if left, hull is concave. Fix by deleting some previous points on hull. • just work backwards till no left turn. • Each point deleted only once, so O(n) • but O(n log n) since must sort by x coord. 2.2 Halfspace intersection Duality. • (a, b) → ax + by +1 = 0. • line through two points becomes point at intersection of 2 lines • pointatdistance d antipodal line at distance 1/d. • intersection of halfspace become convex hull. So, O(n log n)time. 32.3 Segment intersections We saw this one using persistent data structures. • Maintain balanced search tree of segments ordered by current height. • Heap of upcoming “events” (line intersections/crossings) • pull next event from heap, output, swap lines in balanced tree • check swapped lines against neighbors for new intersection events • lemma: next event always occurs between neighbors, so is in heap • note: next event is always in future (never have to backtrack). • so sweep approach valid • and in fact, heap is monotone! 3 Voronoi Diagram Goal: find nearest MIT server terminal to query point. Definitions: • point set p • V (pi) is space closer to pi than anything else • for two points, V (P ) is bisecting line • For 3 points, creates a new “voronoi” point • And for many points, V (pi) is intersection of halfplanes, so a convex poly-hedron • And nonempty of course. • but might be infinite • Given VD, can find nearest neighbor via planar point location: • O(log n) using persistent trees Space complexity: • VD is a planar graph: no two voronoi edges cross (if count voronoi points) • add one point at infinity to make it a proper graph with ends • Euler’s formula: nv − ne + nf =2 4• (nv is voronoi points, not original ones) • But nf = n • Also, every voronoi point has degree at least 3 while every edge has two endpoints. • Thus, 2ne ≥ 3(nv +1) • rewrite 2(n + nv − 2) ≥ 3(nv +1) • So n − 2 ≥ (nv +3)/2, ie nv ≤ 2n − 7 • Gives ne ≤ 3n − 6 Summary: V (P ) has linear space and O(log n)query time. 3.1 Construction VD is dual of projection of lower CH of lifting of points to parabola in 3D. And 3D CH can be done in O(n log n) Can build each vornoi cell in O(n log n), so O(n2 log n). 3.2 Plane Sweep Basic idea: • Build portion of Vor behind sweep line. • problem: not fully determined! may be about to hit a new site. • What is determined? Stuff closer to a point than to line • boundary is a parabola • boundary of know space is pieces of parabolas: “beach line” • as sweep line descends, parabolas descend too. • We need to maintain beach line as “events” change it Descent of one parabola: • sweep line (horizontal) y coord is t • Equation (x − xf )2 +(y − yf)2 =(y − t)2 . • Fix x, find dy/dt • 2(y − yf)dy/dt =2(y − t)(dy/dt − 1) • So dy/dt = −(y − t)/(y − yf) 5• Thus, the higher yf (farther from sweep line) the slower parabola descends. Site event: • Sweep line hits site • creates new degenerate parabola (vertical line) • widens to normal parabola • adds arc piece to beach line. Claim: no other create events. • case 1: one parabola passing through one other – At crossover, two parabolas are tangent. – then “inner” parabola