Algorithms in Java, 4th Edition·Robert Sedgewick and Kevin Wayne·Copyright © 2009·January 26, 2010 8:49:21 AM6.3 Geometric Search‣range search‣space partitioning trees‣intersection searchGeometric objects. Points, lines, intervals, circles, rectangles, polygons, ...This lecture. Intersection among N objects.Example problems.•1D range search.•2D range search.•Find all intersections among h-v line segments.•Find all intersections among h-v rectangles.2Overview‣range search‣space partitioning trees‣intersection search341d range searchExtension of ordered symbol table.•Insert key-value pair.•Search for key k.•Rank: how many keys less than k?•Range search: find all keys between k1 and k2.Application. Database queries.Geometric interpretation.•Keys are point on a line.•How many points in a given interval?insert B Binsert D B Dinsert A A B Dinsert I A B D Iinsert H A B D H Iinsert F A B D F H Iinsert P A B D F H I Pcount G to K 2search G to K H I51d range search: implementationsOrdered array. Slow insert, binary search for lo and hi to find range.Hash table. No reasonable algorithm (key order lost in hash).BST. All operations fast.N = # keysR = # keys that matchdata structureinsertrankrange countrange searchordered arrayNlog Nlog NR + log Nhash table1NNNBSTlog Nlog Nlog NR + log NRange 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).Worst-case running time. R + log N (assuming BST is balanced).61d range search: BST implementationblack keys arein the rangered keys are used in comparesbut are not in the rangeACEHLMPRSXsearching in the range [F..T]Range search in a BST72d orthogonal range searchExtension of ordered symbol-table to 2d keys.•Insert a 2d key.•Search for a 2d key.•Range search: find all keys that lie in a 2d range?Applications. Networking, circuit design, databases.Geometric interpretation.•Keys are point in the plane.•How many points in a given h-v rectangle.rectangle is axis-aligned82d orthogonal range search: grid implementationGrid implementation.•Divide space into M-by-M 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 those squares that intersect 2d range query.LBRT92d orthogonal range search: grid implementation costsSpace-time tradeoff.•Space: M2 + N.•Time: 1 + N / M2 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: !N-by-!N grid.Running time. [if points are evenly distributed]•Initialize: O(N).•Insert: O(1).•Range: O(1) per point in range.M ~ !N LBRTGrid implementation. Fast, simple solution for well-distributed points.Problem. Clustering a well-known phenomenon in geometric data.Lists are too long, even though average length is short.Need data structure that gracefully adapts to data.10ClusteringGrid implementation. Fast, simple solution for well-distributed points.Problem. Clustering a well-known phenomenon in geometric data.Ex. USA map data.11Clusteringhalf the squares are emptyhalf the points arein 10% of the squares13,000 points, 1000 grid squares‣range search‣space partitioning trees‣intersection search12Use a tree to represent a recursive subdivision of 2D space.Quadtree. Recursively divide space into four quadrants.2d tree. Recursively divide space into two halfplanes. BSP tree. Recursively divide space into two regions.13Space-partitioning treesGrid2D treeQuadtreeBSP tree14Space-partitioning trees: applicationsApplications.•Ray tracing.•2d range search.•Flight simulators.•N-body simulation.•Collision detection.•Astronomical databases. •Nearest neighbor search. •Adaptive mesh generation.•Accelerate rendering in Doom.•Hidden surface removal and shadow casting. Grid2D treeQuadtreeBSP treeIdea. Recursively divide space into 4 quadrants. Implementation. 4-way tree (actually a trie).Benefit. Good performance in the presence of clustering.Drawback. Arbitrary depth!15Quadtreeabcefghdpublic class QuadTree{ private Quad quad; private Value val; private QuadTree NW, NE, SW, SE;}(01.., 00..)(0..., 1...)ab cd e f ghSENWSWNE16Quadtree: larger examplehttp://en.wikipedia.org/wiki/Image:Point_quadtree.svg17Quadtree: 2d range searchRange search. Find all keys in a given 2D range.•Recursively find all keys in NE quad (if any could fall in range).•Recursively find all keys in NW quad (if any could fall in range).•Recursively find all keys in SE quad (if any could fall in range).•Recursively find all keys in SW quad (if any could fall in range).Typical running time. R + log N.abcefghdab cdefgh18N-body simulationGoal. Simulate the motion of N particles, mutually affected by gravity. Brute force. For each pair of particles, compute force.F =Gm1m2r219Subquadratic N-body simulationKey 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 particle.20Barnes-Hut algorithm for N-body simulation.Barnes-Hut.•Build quadtree with N particles as external nodes.•Store center-of-mass of subtree in each internal node.•To compute total force acting on a particle, traverse tree, but stop as soon as distance from particle to quad is sufficiently large.21Curse of dimensionalityRange search / nearest neighbor in k dimensions?Main application. Multi-dimensional databases.3d space. Octrees: recursively divide 3d space into 8 octants.100d space. Centrees: recursively divide 100d space into 2100 centrants???Raytracing with octreeshttp://graphics.cs.ucdavis.edu/~gregorsk/graphics/275.htmlRecursively partition plane into two halfplanes.222d tree1234678910512871093465Implementation. BST, but alternate using x- and y-coordinates as key.•Search gives rectangle containing point.•Insert further subdivides the plane.232d treeeven levelsppointsleft of ppointsright of ppqpointsbelow qpointsabove qodd levelsq128710934651234678910512871093465Range search. Find all points in a query axis-aligned rectangle.•Check if point in node lies in given rectangle.•Recursively search left/top
View Full Document