Home PageTitle PageContentsJJ IIJ IPage 1 of 7Go BackFull ScreenCloseQuitRange Search: The Scenario• Input Q is an orthogonal range(for the time being)– Output the points in Q– Output the number ofpoints• Can be used (how?) to helpsolve the problem “Find thenearest McDonald within a 20mile radius of a query p”• Straightforward solution: Check if each of n points are inside Q• Can we preprocess the points so that the query can be answeredmore efficiently?Home PageTitle PageContentsJJ IIJ IPage 2 of 7Go BackFull ScreenCloseQuitAn Idea That Does Not HelpAssume points stored in a kd-tree• Locating the lower left corner of q in kd-tree does not help too much.We fall of k and the path taken (a, h, i, j, k) contains some relevantnodes and some irrelevant nodesHome PageTitle PageContentsJJ IIJ IPage 3 of 7Go BackFull ScreenCloseQuitAlternate Idea• Instead, let C is the region as-sociated with a node.• If the query Q rectangle– Is disjoint from C– Completely contains C• We do not need to process thepossibly many points within C• In the example, this situationarises for the region associatedwith node b• What should we do if the query Q does not satisfy the two condi-tions?Home PageTitle PageContentsJJ IIJ IPage 4 of 7Go BackFull ScreenCloseQuitSmaller Easier Queries• Q.contains (Point p) (p:point associated with a kdtreenode)• Q.contains (Rectangle C)(C: rectangle associated with akdtree node)• Q.isDisjoint (Rectangle C)• Also need to be able to split the rectangle CHome PageTitle PageContentsJJ IIJ IPage 5 of 7Go BackFull ScreenCloseQuitRange Search: CodeSet searchKDTree (KDNode n , Query Q, int cd ) {i f ( n = n ul l ) return {};e l s e i f (Q. i s D i s j o i n t (n ) ) return {};e l s e i f (Q. c on ta i ns (n ) } return A l l P oi n ts ( n ) ;e l s e {Set middle = Q. c on ta in s (n . data ) ;Set l e f t = searchKDTree ( n . l e f t , Q, cd +1);Set r i g h t = searchKDTree ( n . r i g h t , Q, cd +1);return union ( union ( l e f t , r i g h t ) , middle )}Home PageTitle PageContentsJJ IIJ IPage 6 of 7Go BackFull ScreenCloseQuitExample• Search takes O(√n) time if tree is balanced.• A range stabs a node if it overlaps the rectangle associated with thenode without being contained in the cell.Home PageTitle PageContentsJJ IIJ IPage 7 of 7Go BackFull ScreenCloseQuitRange Search: Proof• Running time is a function of how many nodes get stabbed• Any vertical or horizontal line stabs at most O(√n) nodes– Consider a vertical line x = x0.∗ If the cutting dimension is x, then the line stabs either theleft child, or the right child but not both.∗ If it fails to stab a child, it fails to stab the descendents ofthat child.– Otherwise it stabs both children.– After descending to the grandchildren level, at most four morenodes are stabbed.– In the worst case, root is stabbed, 4 nodes are stabbed at thegrandchildren level, 8 nodes are stabbed at level 6– At most 2inodes at level