Algorithms on gridsGrids in computer scienceSlide 3Grids for geometric proximityClosest pairGrids for pointsSub-problemAlgorithmSlide 9Slide 10AnalysisSlide 12k-Enclosing minimum diskNon-uniform gridFinite centersSlide 16Correctness10/2/2006 1Algorithms on gridsNatasha GelfandGeometry SeminarFall 200610/2/2006 Geometry Seminar: Algorithms on Grids 2Grids in computer science10/2/2006 Geometry Seminar: Algorithms on Grids 3Grids in computer science• Graphics and vision•Collision detection, point location•Simulation10/2/2006 Geometry Seminar: Algorithms on Grids 4Grids for geometric proximity•Isolate and localize interesting events–Proximity is local•“Uniform” grids–Closest pair, k-Minimum enclosing disk•Adaptive grids–quadtrees10/2/2006 Geometry Seminar: Algorithms on Grids 5Closest pair•Given: n points in the plane•Return pair of pointsrealizing10/2/2006 Geometry Seminar: Algorithms on Grids 6•Computing the grid takes linear timeGrids for points10/2/2006 Geometry Seminar: Algorithms on Grids 7Sub-problem•Given a set P and a distance r, verify in linear time if CP(P)<r or CP(P) > r–Insert points sequentially–If CP(P) < r, p, q are in the same orneighboring cells–Can we search a cellin constant time?r10/2/2006 Geometry Seminar: Algorithms on Grids 8Algorithm•If some cell contains more than 9 points, then CP(P)<r•Algorithm:–Insert points into the grid–If cell(p) contains more than 9 points, return CP(P) < r10/2/2006 Geometry Seminar: Algorithms on Grids 9Algorithm•If some cell contains more than 9 points, then CP(P)<r•Algorithm:–Insert points into the grid–If cell(p) contains more than 9 points, return CP(P) < r–Otherwise, compute•Constant time per point,running time O(n)r10/2/2006 Geometry Seminar: Algorithms on Grids 10Closest pair•Permute points P=<p1, p1, … , pn>•Let ri = CP({p1, …, pi})–Can check if ri<ri-1 in linear time•Good case: ri = ri-1–Grid is already built, check in O(1) time•Bad case: ri < ri-1–Rebuild grid, O(i) time•Trivial bound: O(nk), when closest pair changes k times10/2/2006 Geometry Seminar: Algorithms on Grids 11Analysis•Let Xi = 1 if ri · ri-1, and 0 otherwise•Running time:10/2/2006 Geometry Seminar: Algorithms on Grids 12Analysis•Bound Pr[Xi = 1] = Pr[ri < ri-1]–Likelihood that pi realizes CP(Pi)•Expected running time10/2/2006 Geometry Seminar: Algorithms on Grids 13k-Enclosing minimum disk•Disk of minimum radius that contains k points•Brute force O(nk)•2-Opt algorithm: r(P,k) · 2ropt(P,k) k=3k=410/2/2006 Geometry Seminar: Algorithms on Grids 14Non-uniform grid•Partition P into horizontal strips with at most k/4 points in each strip–Recursive median partitioning –O(n/k) stripsGRunning time:T(n) = n + 2T(n/2)Stop at n < k/4O(nlog(n/k))10/2/2006 Geometry Seminar: Algorithms on Grids 15Finite centers•Claim: Dopt(P,k) contains at least one intersection point of G•Pf: By contradiction: At most k/2 pointsDopt(P,k)k/4 pointsk/4 pointsk points10/2/2006 Geometry Seminar: Algorithms on Grids 16Algorithm•For each grid intersection point g2G–Compute smallest circle centered at p with k points–k-th order statistic of {||p, g||}–Expected time O(n)–Return the best of (n/k)2 candidates•Running time: O(n(n/k)2)10/2/2006 Geometry Seminar: Algorithms on Grids 17Correctness•2-Opt: r(P,k) ·
View Full Document
Unlocking...