Question? Leave a message!




GEOMETRIC APPLICATIONS OF Binary Search Trees (BSTs)

GEOMETRIC APPLICATIONS OF Binary Search Trees (BSTs)
ROBERT SEDGEWICK KEVIN WAYNE Algorithms GEOMETRIC APPLICATIONS OF BSTS 1d range search ‣ line segment intersection ‣ kd trees ‣ Algorithms FOUR TH EDITION interval search trees ‣ rectangle intersection ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduOverview This lecture. Intersections among geometric objects. 2d orthogonal range search orthogonal rectangle intersection Applications. CAD, games, movies, virtual reality, databases, GIS, .… Efficient solutions. Binary search trees (and extensions). 2GEOMETRIC APPLICATIONS OF BSTS 1d range search ‣ line segment intersection ‣ kd trees ‣ Algorithms interval search trees ‣ rectangle intersection ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.edu1d range search Extension of ordered symbol table. Insert keyvalue pair. Search for key k. Delete key k. Range search: find all keys between k and k . 1 2 Range count: number of keys between k and k . 1 2 Application. Database queries. insert B B insert D B D insert A A B D Geometric interpretation. insert I A B D I insert H A B D H I Keys are point on a line. insert F A B D F H I Find/count points in a given 1d interval. insert P A B D F H I P search G to K H I count G to K 2 41d range search: elementary implementations Unordered list. Fast insert, slow range search. Ordered array. Slow insert, binary search for k and k to do range search. 1 2 order of growth of running time for 1d range search data structure insert range count range search unordered list 1 N N ordered array N log N R + log N goal log N log N R + log N N = number of keys R = number of keys that match 51d range count: BST implementation 1d range count. How many keys between lo and hi 6 rank S 2 7 E X 5 0 A R 3 1 C H 4 M public int size(Key lo, Key hi) if (contains(hi)) return rank(hi) rank(lo) + 1; else return rank(hi) rank(lo); number of keys hi Proposition. Running time proportional to log N. Pf. Nodes examined = search path to lo + search path to hi. 61d range search: BST implementation 1d range search. Find all keys between lo and hi. Recursively find all keys in left subtree (if any could fall in range). Check key in current node. Recursively find all keys in right subtree (if any could fall in range). searching in the range F..T red keys are used in compares but are not in the range S E X A R H C M L P black keys are in the range Range search in a BST Proposition. Running time proportional to R + log N. Pf. Nodes examined = search path to lo + search path to hi + matches. 7GEOMETRIC APPLICATIONS OF BSTS 1d range search ‣ line segment intersection ‣ kd trees ‣ Algorithms interval search trees ‣ rectangle intersection ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduOrthogonal line segment intersection Given N horizontal and vertical line segments, find all intersections. Quadratic algorithm. Check all pairs of line segments for intersection. Nondegeneracy assumption. All x and ycoordinates are distinct. 9Orthogonal line segment intersection: sweepline algorithm Sweep vertical line from left to right. xcoordinates define events. hsegment (left endpoint): insert ycoordinate into BST. 3 3 4 2 2 1 1 0 0 ycoordinates 10Orthogonal line segment intersection: sweepline algorithm Sweep vertical line from left to right. xcoordinates define events. hsegment (left endpoint): insert ycoordinate into BST. hsegment (right endpoint): remove ycoordinate from BST. 3 3 4 2 1 1 0 0 ycoordinates 11Orthogonal line segment intersection: sweepline algorithm Sweep vertical line from left to right. xcoordinates define events. hsegment (left endpoint): insert ycoordinate into BST. hsegment (right endpoint): remove ycoordinate from BST. vsegment: range search for interval of yendpoints. 3 3 1d range 4 search 2 1 1 0 0 ycoordinates 12Orthogonal line segment intersection: sweepline analysis Proposition. The sweepline algorithm takes time proportional to N log N + R to find all R intersections among N orthogonal line segments. Pf. N log N Put xcoordinates on a PQ (or sort). N log N Insert ycoordinates into BST. Delete ycoordinates from BST. N log N Range searches in BST. N log N + R Bottom line. Sweep line reduces 2d orthogonal line segment intersection search to 1d range search. 13GEOMETRIC APPLICATIONS OF BSTS 1d range search ‣ line segment intersection ‣ kd trees ‣ Algorithms interval search trees ‣ rectangle intersection ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.edu2d orthogonal range search Extension of ordered symboltable to 2d keys. Insert a 2d key. Delete a 2d key. Search for a 2d key. Range search: find all keys that lie in a 2d range. Range count: number of keys that lie in a 2d range. Applications. Networking, circuit design, databases, ... Geometric interpretation. Keys are point in the plane. Find/count points in a given hv rectangle rectangle is axisaligned 152d orthogonal range search: grid implementation Grid implementation. Divide space into MbyM grid of squares. Create list of points contained in each square. Use 2d array to directly index relevant square. Insert: add (x, y) to list for corresponding square. Range search: examine only squares that intersect 2d range query. RT LB 162d orthogonal range search: grid implementation analysis Spacetime tradeoff. 2 Space: M + N. 2 Time: 1 + N / M per square examined, on average. Choose grid square size to tune performance. Too small: wastes space. Too large: too many points per square. Rule of thumb: √Nby√N grid. RT Running time. if points are evenly distributed Initialize data structure: N. choose M √N Insert point: 1. Range search: 1 per point in range. LB 17Clustering Grid implementation. Fast, simple solution for evenlydistributed points. Problem. Clustering a wellknown phenomenon in geometric data. Lists are too long, even though average length is short. Need data structure that adapts gracefully to data. 18Clustering Grid implementation. Fast, simple solution for evenlydistributed points. Problem. Clustering a wellknown phenomenon in geometric data. Ex. USA map data. 13,000 points, 1000 grid squares half the squares are empty half the points are in 10 of the squares 19Spacepartitioning trees Use a tree to represent a recursive subdivision of 2d space. Grid. Divide space uniformly into squares. 2d tree. Recursively divide space into two halfplanes. Quadtree. Recursively divide space into four quadrants. BSP tree. Recursively divide space into two regions. Grid 2d tree Quadtree BSP tree 20Spacepartitioning trees: applications Applications. Ray tracing. 2d range search. Flight simulators. Nbody simulation. Collision detection. Astronomical databases. Nearest neighbor search. Adaptive mesh generation. Accelerate rendering in Doom. Hidden surface removal and shadow casting. Grid 2d tree Quadtree BSP tree 212d tree construction Recursively partition plane into two halfplanes. 8 1 3 6 2 9 3 8 4 6 7 1 9 10 5 5 2 7 10 4 222d tree implementation Data structure. BST, but alternate using x and ycoordinates as key. Search gives rectangle containing point. Insert further subdivides the plane. q p q p points points points points below q above q left of p right of p odd levels even levels 8 1 6 9 3 3 2 1 5 2 8 4 6 7 7 9 10 5 10 4 232d tree demo: range search Goal. Find all points in a query axisaligned rectangle. Check if point in node lies in given rectangle. Recursively search left/bottom (if any could fall in rectangle). Recursively search right/top (if any could fall in rectangle). 8 1 3 2 6 9 3 8 4 6 7 1 9 5 5 10 2 7 10 4 242d tree demo: range search Goal. Find all points in a query axisaligned rectangle. Check if point in node lies in given rectangle. Recursively search left/bottom (if any could fall in rectangle). Recursively search right/top (if any could fall in rectangle). 8 1 3 2 6 9 3 8 4 6 7 1 9 5 5 10 2 7 10 4 done 25Range search in a 2d tree analysis Typical case. R + log N. Worst case (assuming tree is balanced). R + √N. 8 1 3 2 6 9 3 8 4 6 7 1 9 5 5 10 2 7 10 4 262d tree demo: nearest neighbor Goal. Find closest point to query point. 8 1 3 2 6 9 query point 3 8 4 6 7 1 9 5 5 10 2 7 10 4 272d tree demo: nearest neighbor Check distance from point in node to query point. Recursively search left/bottom (if it could contain a closer point). Recursively search right/top (if it could contain a closer point). Organize method so that it begins by searching for query point. 8 1 3 2 6 9 3 8 4 6 7 1 9 5 5 10 2 7 10 4 nearest neighbor = 5 28Nearest neighbor search in a 2d tree analysis Typical case. log N. Worst case (even if tree is balanced). N. 8 1 3 2 6 9 3 8 4 6 7 1 9 5 5 10 2 7 10 4 nearest neighbor = 5 30 29Flocking birds Q. What "natural algorithm" do starlings, migrating geese, starlings, cranes, bait balls of fish, and flashing fireflies use to flock http://www.youtube.com/watchv=XHgroCeKbE 30Flocking boids Craig Reynolds, 1986 Boids. Three simple rules lead to complex emergent flocking behavior: Collision avoidance: point away from k nearest boids. Flock centering: point towards the center of mass of k nearest boids. Velocity matching: update velocity to the average of k nearest boids. 31Kd tree Kd tree. Recursively partition kdimensional space into 2 halfspaces. Implementation. BST, but cycle through dimensions ala 2d trees. p level ≡ i (mod k) points points th whose i th whose i coordinate coordinate is greater than p’s is less than p’s Efficient, simple data structure for processing kdimensional data. Widely used. Adapts well to highdimensional and clustered data. Discovered by an undergrad in an algorithms class Jon Bentley 32Nbody simulation Goal. Simulate the motion of N particles, mutually affected by gravity. Gm m 1 2 F = Brute force. For each pair of particles, compute force: 2 r 2 Running time. Time per step is N . http://www.youtube.com/watchv=ua7YlN4eLw 33Appel's algorithm for Nbody simulation Key idea. Suppose particle is far, far away from cluster of particles. Treat cluster of particles as a single aggregate particle. Compute force between particle and center of mass of aggregate. 34Appel's algorithm for Nbody simulation Build 3dtree with N particles as nodes. Store centerofmass of subtree in each node. To compute total force acting on a particle, traverse tree, but stop as soon as distance from particle to subdivision is sufficiently large. J. ScI. COMPUT. 1985 for Industrial and Mathematics SIAM STAT. Society Applied Vol. No. 1985 O08 6, 1, January AN EFFICIENT PROGRAM FOR MANYBODY SIMULATION ANDREW W. APPEL Abstract. The simulation ofN particles interacting in a gravitational force field is useful in astrophysics, but such simulations become for N. costly large Representing the universe as a tree structure with the particles at the leaves and internal nodes labeled with the centers of mass of their descendants allows several simultaneous attacks on the computation time required by the problem. These approaches range from an ’) with algorithmic changes (replacing O(N algorithm an algorithm whose timecomplexity is believed to be O(N log N)) to data structure modifications, and hardware modifications. The codetuning, changes reduced the running time of a large problem (N 10,000) by a factor of four hundred. This describes paper both the and the particular program methodology underlying such speedups. 1. Introduction. IsaacNewton calculated the behavior oftwo particles interacting the force of buthewasunable to solve the for three through gravity, equations particles. In this he was not alone 7, p. 634, and systems of three or more particles can be solved Iterative at discrete only numerically. methods are usually used, computing each time interval the force on each particle, and then the new velocities and computing Impact. Running time per step is for each N log N ⇒ enables new research. positions particle. A naive implementation of an iterative manybody simulator is computationally for numbers of where means of very expensive large particles, "expensive" days Cray1 35 time or a of VAX This the an year time. paper describes development of efficient in which several of the were made faster. The initial program aspects computation was the use of a new with lower time the use step algorithm asymptotic complexity; of a better is often the to achieve the in algorithm way greatest gains speed 2. Since attracts each of the others the force of there are every particle by gravity, O(N2) interactions to compute for iteration. Furthermore, for the same reasons every that the closedform for small distances the force is integral diverges (since proportional to the of the inverse square distance between two bodies), the discrete time interval must be made small in the case that two close to each extremely particles pass very other. are two on the attack These the problems which algorithmic concentrated. By the use of an data structure, each iteration can be done in time believed appropriate to be O(N log N), and the time intervals be made much larger, thus reducing may the number of iterations The is to in required. algorithm applicable Nbody problems any force field with no dipole moments; it is particularly useful when there is a severe in the distribution or when a is nonuniformity particle large dynamic range required when several scales in the simulation are of (that is, distance interest). The use of an with a better time a algorithm asymptotic complexity yielded in time. Four additional attacks on the significant improvement running problem were also undertaken, each of which yielded at least a factor of two improvement in speed. These attacks from into ranged insights the physics down to handcoding a routine in By at levels, the execution time of a assembly language. finding savings many design simulation was reduced from hours to 20 hours. large (an estimated) 8,000 (actual) The program was used to open problems in evidence to investigate cosmology, giving a model of the universe with random initial mass distribution and mass support high density. Received by the editors March 24, 1983, and in revised form October 1, 1983. r Computer Science Department, 15213. This CarnegieMellon University, Pittsburgh, Pennsylvania research a National Science Graduate Student and the office was supported by Foundation Fellowship by of Naval Research under N0001476C0370. grant 85GEOMETRIC APPLICATIONS OF BSTS 1d range search ‣ line segment intersection ‣ kd trees ‣ Algorithms interval search trees ‣ rectangle intersection ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.edu1d interval search 1d interval search. Data structure to hold set of (overlapping) intervals. Insert an interval ( lo, hi ). Search for an interval ( lo, hi ). Delete an interval ( lo, hi ). Interval intersection query: given an interval ( lo, hi ), find all intervals (or one interval) in data structure that intersects ( lo, hi ). Q. Which intervals intersect ( 9, 16 ) A. ( 7, 10 ) and ( 15, 18 ). (7, 10) (21, 24) (17, 19) (5, 8) (4, 8) (15, 18) 371d interval search API public class public class public class IntervalSTKey extends ComparableKey, Value IntervalSTKey extends ComparableKey, Value IntervalSTKey extends ComparableKey, Value IntervalST() create interval search tree void put(Key lo, Key hi, Value val) put intervalvalue pair into ST Value get(Key lo, Key hi) value paired with given interval void delete(Key lo, Key hi) delete the given interval IterableValue intersects(Key lo, Key hi) all intervals that intersect (lo, hi) Nondegeneracy assumption. No two intervals have the same left endpoint. 38Interval search trees Create BST, where each node stores an interval ( lo, hi ). Use left endpoint as BST key. Store max endpoint in subtree rooted at node. 24 (17, 19) 24 18 (21, 24) (5, 8) binary search tree (left endpoint is key) 18 8 (15, 18) (4, 8) max endpoint in subtree rooted at node (7, 10) 10 39Interval search tree demo: insertion To insert an interval ( lo, hi ) : Insert into BST, using lo as the key. Update max in each node on search path. insert interval (16, 22) 24 (17, 19) 24 18 (21, 24) (5, 8) 18 8 (15, 18) (4, 8) (7, 10) 10 40Interval search tree demo: insertion To insert an interval ( lo, hi ) : Insert into BST, using lo as the key. Update max in each node on search path. insert interval (16, 22) 24 (17, 19) 24 22 (21, 24) (5, 8) 22 8 (15, 18) (4, 8) (16, 22) 22 (7, 10) 10 41Interval search tree demo: intersection To search for any one interval that intersects query interval ( lo, hi ) : If interval in node intersects query interval, return it. Else if left subtree is null, go right. Else if max endpoint in left subtree is less than lo, go right. Else go left. interval intersection 24 (17, 19) search for (21, 23) 24 22 (21, 24) (5, 8) 22 8 (15, 18) (4, 8) compare (21, 23) to (16, 22) (intersection) (16, 22) 22 (7, 10) (21, 23) 10 42Search for an intersecting interval: implementation To search for any one interval that intersects query interval ( lo, hi ) : If interval in node intersects query interval, return it. Else if left subtree is null, go right. Else if max endpoint in left subtree is less than lo, go right. Else go left. Node x = root; while (x = null) if (x.interval.intersects(lo, hi)) return x.interval; else if (x.left == null) x = x.right; else if (x.left.max lo) x = x.right; else x = x.left; return null; 43Search for an intersecting interval: analysis To search for any one interval that intersects query interval ( lo, hi ) : If interval in node intersects query interval, return it. Else if left subtree is null, go right. Else if max endpoint in left subtree is less than lo, go right. Else go left. Case 1. If search goes right, then no intersection in left. Pf. Suppose search goes right and left subtree is non empty. Since went right, we have max lo. For any interval (a, b) in left subtree of x, we have b ≤ max lo. max (c, max) reason for going right definition of max (a, b) (lo, hi) Thus, (a, b) will not intersect ( lo, hi ). right subtree of x left subtree of x 44Search for an intersecting interval: analysis To search for any one interval that intersects query interval ( lo, hi ) : If interval in node intersects query interval, return it. Else if left subtree is null, go right. Else if max endpoint in left subtree is less than lo, go right. Else go left. Case 2. If search goes left, then there is either an intersection in left subtree or no intersections in either. Pf. Suppose no intersection in left. Since went left, we have lo ≤ max. Then for any interval (a, b) in right subtree of x, max hi c ≤ a ⇒ no intersection in right. (c, max) (lo, hi) (a, b) intervals sorted no intersections by left endpoint in left subtree right subtree of x left subtree of x 45Interval search tree: analysis Implementation. Use a redblack BST to guarantee performance. easy to maintain auxiliary information (log N extra work per operation) interval best operation brute search tree in theory insert interval 1 log N log N find interval N log N log N delete interval N log N log N find any one interval N log N log N that intersects (lo, hi) find all intervals N R log N R + log N that intersects (lo, hi) order of growth of running time for N intervals 46GEOMETRIC APPLICATIONS OF BSTS 1d range search ‣ line segment intersection ‣ kd trees ‣ Algorithms interval search trees ‣ rectangle intersection ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduOrthogonal rectangle intersection Goal. Find all intersections among a set of N orthogonal rectangles. Quadratic algorithm. Check all pairs of rectangles for intersection. 3 2 0 1 Nondegeneracy assumption. All x and ycoordinates are distinct. 48Microprocessors and geometry Early 1970s. microprocessor design became a geometric problem. Very Large Scale Integration (VLSI). ComputerAided Design (CAD). Designrule checking. Certain wires cannot intersect. Certain spacing needed between different types of wires. Debugging = orthogonal rectangle intersection search. 49Algorithms and Moore's law "Moore’s law." Processing power doubles every 18 months. 197x: check N rectangles. 197(x+1.5): check 2 N rectangles on a 2xfaster computer. Gordon Moore Bootstrapping. We get to use the faster computer for bigger circuits. But bootstrapping is not enough if using a quadratic algorithm: 197x: takes M days. 197(x+1.5): takes (4 M) / 2 = 2 M days. () quadratic 2xfaster algorithm computer Bottom line. Linearithmic algorithm is necessary to sustain Moore’s Law. 50Orthogonal rectangle intersection: sweepline algorithm Sweep vertical line from left to right. xcoordinates of left and right endpoints define events. Maintain set of rectangles that intersect the sweep line in an interval search tree (using yintervals of rectangle). Left endpoint: interval search for yinterval of rectangle; insert yinterval. Right endpoint: remove yinterval. 3 3 2 2 0 0 1 1 ycoordinates 51Orthogonal rectangle intersection: sweepline analysis Proposition. Sweep line algorithm takes time proportional to N log N + R log N to find R intersections among a set of N rectangles. Pf. N log N Put xcoordinates on a PQ (or sort). N log N Insert yintervals into ST. N log N Delete yintervals from ST. Interval searches for yintervals. N log N + R log N Bottom line. Sweep line reduces 2d orthogonal rectangle intersection search to 1d interval search. 52Geometric applications of BSTs problem example solution BST 1d range search 2d orthogonal line sweep line reduces to 1d range search segment intersection kd tree kd range search interval search tree 1d interval search 2d orthogonal sweep line reduces to 1d interval search rectangle intersection 53
sharer
Presentations
Free
Document Information
Category:
Presentations
User Name:
Dr.BenjaminClark
User Type:
Teacher
Country:
United States
Uploaded Date:
21-07-2017