1Geometric Algorithmsrange searchquad and kd treesintersection searchVLSI rules checkReferences: Algorithms in C (2nd edition), Chapters 26-27 http://www.cs.princeton.edu/introalgsds/73range http://www.cs.princeton.edu/introalgsds/74intersection2OverviewTypes of data. Points, lines, planes, polygons, circles, ...This lecture. Sets of N objects.Geometric problems extend to higher dimensions.•Good algorithms also extend to higher dimensions.•Curse of dimensionality.Basic problems.•Range searching.•Nearest neighbor.•Finding intersections of geometric objects.3range searchquad and kd treesintersection searchVLSI rules check41D Range SearchExtension to symbol-table ADT with comparable keys.•Insert key-value pair.•Search for key k.•How many records have keys between k1 and k2?•Iterate over all records with keys between k1 and k2.Application: database queries.Geometric intuition.•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: implementationsRange search. How many records have keys between k1 and k2?Ordered array. Slow insert, binary search for k1 and k2 to find range.Hash table. No reasonable algorithm (key order lost in hash).BST. In each node x, maintain number of nodes in tree rooted at x. Search for smallest element  k1 and largest element  k2. log NNlog Ncountinsert rangeordered array N R + log Nhash table 1 NBST log N R + log Nnodes examinedwithin intervalnot touchedN = # recordsR = # records that match62D Orthogonal Range SearchExtension to symbol-table ADT with 2D keys.•Insert a 2D key.•Search for a 2D key.•Range search: find all keys that lie in a 2D range?•Range count: how many keys lie in a 2D range?Applications: networking, circuit design, databases.Geometric interpretation.•Keys are point in the plane•Find all points in a given h-v rectangle72D Orthogonal range Search: Grid implementationGrid implementation. [Sedgewick 3.18]•Divide space into M-by-M grid of squares.•Create linked list for each square.•Use 2D array to directly access relevant square. •Insert: insert (x, y) into corresponding grid square.•Range search: examine only those grid squares that could have points in the rectangle.LBRT82D Orthogonal Range Search: Grid Implementation CostsSpace-time tradeoff.•Space: M2 + N.•Time: 1 + N / M2 per grid cell examined on average.Choose grid square size to tune performance.•Too small: wastes space.•Too large: too many points per grid 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.LBRTM  N9ClusteringGrid implementation. Fast, simple solution for well-distributed points.Problem. Clustering is a well-known phenomenon in geometric data.Ex: USA map data. 13,000 points, 1000 grid squares.Lists are too long, even though average length is short.Need data structure that gracefully adapts to data.half the squares are emptyhalf the points arein 10% of the squares10range searchquad and kd treesintersection searchVLSI rules check11Space Partitioning TreesUse a tree to represent a recursive subdivision of d-dimensional space.BSP tree. Recursively divide space into two regions.Quadtree. Recursively divide plane into four quadrants.Octree. Recursively divide 3D space into eight octants.kD tree. Recursively divide k-dimensional space into two half-spaces. [possible but much more complicated to define Voronoi-based structures]Applications.•Ray tracing.•Flight simulators.•N-body simulation.•Collision detection. •Astronomical databases. •Adaptive mesh generation.•Accelerate rendering in Doom.•Hidden surface removal and shadow casting. GridQuadtreekD treeBSP tree12QuadtreeRecursively partition plane into 4 quadrants. Implementation: 4-way tree.Primary reason to choose quad trees over grid methods: good performance in the presence of clusteringabcefghda hdgebcfpublic class QuadTree{ private Quad quad; private Value value; private QuadTree NW, NE, SW, SE;}actually a triepartitioning on bits of coordinates(01..., 00...)(0..., 1...)13Curse 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 into 2100 centrants???Raytracing with octreeshttp://graphics.cs.ucdavis.edu/~gregorsk/graphics/275.html142D TreesRecursively partition plane into 2 halfplanes. Implementation: BST, but alternate using x and y coordinates as key.•Search gives rectangle containing point.•Insert further subdivides the plane.even levelsqppointsleft of ppointsright of ppointsbelow qpointsabove qodd levelspq15Near Neighbor SearchUseful extension to symbol-table ADT for records with metric keys.•Insert a k dimensional point.•Near neighbor search: given a point p, which point in data structure is nearest to p?Need concept of distance, not just ordering.kD trees provide fast, elegant solution.•Recursively search subtrees that couldhave near neighbor (may search both).•O(log N) ?Yes, in practice(but not proven)16kD TreeskD tree. Recursively partition k-dimensional space into 2 halfspaces. Implementation: BST, but cycle through dimensions ala 2D trees.Efficient, simple data structure for processing k-dimensional data.•adapts well to clustered data.•adapts well to high dimensional data.•widely used.•discovered by an undergrad in an algorithms class!level  i (mod k)pointswhose ithcoordinateis less than p’spointswhose ithcoordinateis greater than p’sp17SummaryBasis of many geometric algorithms: search in a planar subdivision.grid 2D tree Voronoi diagramintersectinglinesbasisN h-v linesN points N pointsN linesrepresentation2D arrayof N listsN-node BSTN-node multilist~N-node BSTcells ~N squares N rectangles N polygons~N trianglessearch cost 1 log N log N log Nextend to kD? too many cells easycells too complicateduse (k-1)Dhyperplane18range searchquad and kd treesintersection searchVLSI rules check19Search for intersectionsProblem. Find all intersecting pairs among set of N geometric objects.Applications. CAD, games, movies, virtual