sec spatial data structures figure function incircle must check the euclidean distance between record and the query point it is possible for record to have xand ycoordinates each within the query distance of the query point cyet have itself lie outside the query circle if the search process reaches node whose key value for the discriminator is more than above the corresponding value in the search keythen it is not possible that any record in the right subtree can be within distance of the search key because all key values in that dimension are always too great similarlyif the current node' key value in the discriminator is less than that for the search key valuethen no record in the left subtree can be within the radius in such casesthe subtree in question need not be searchedpotentially saving much time in the average casethe number of nodes that must be visited during range query is linear on the number of data records that fall within the query circle example find all cities in the - tree of figure within units of the point ( the search begins with the root nodewhich contains record because ( is exactly units from the search pointit will be reported the search procedure then determines which branches of the tree to take the search circle extends to both the left and the right of ' (verticaldividing lineso both branches of the tree must be searched the left subtree is processed first hererecord is checked and found to fall within the search circle because the node storing has no childrenprocessing of the left subtree is complete processing of ' right subtree now begins the coordinates of record are checked and found not to fall within the circle thusit should not be reported howeverit is possible that cities within ' subtrees could fall within the search circle even if does not as is at level the discriminator at this level is the -coordinate because no record in ' left subtree ( records above ccould possibly be in the search circle thusc' left subtree (if it had oneneed not be searched howevercities in ' right subtree could fall within