Method for searching for a given point in regions defined by attribute ranges, then sorted by lower and upper range values and dimension

Claim 1

A method for computer sorting and making a search of a plurality of regions, each region expressed as at least one range, each range having a lower and an upper value, wherein the lower and upper values may be equal, and no two regions have both the same number of ranges and all corresponding ranges overlap, and wherein the search will determine whether a point, expressed as a plurality of coordinates, is included within one of the regions, the search being successful when both the number of coordinates of the point is equal to the number of ranges in a region and each coordinate of the point is within each corresponding range within the region, comprising the steps of: (a) creating a first sorted list of the regions by: (i) arranging the regions by the number of ranges within each region, and (ii) sub-arranging the regions having an equal number of ranges by the lower value of the first range in each region, and for regions having an equal number of ranges and an equal lower value for the first range, proceeding to a comparison of the lower value for each successive corresponding range in the regions until two corresponding lower values are unequal; (b) creating a second sorted list of the regions by repeating step (a) using the upper values for the ranges instead of the lower values; (c) performing a preliminary search on the first sorted list to create a first sublist of regions where the point could be located, searching first for regions that have the same number of ranges as the point has coordinates, and thereafter searching said regions having the same number of ranges as the point has coordinates, by comparing coordinate values of the point with the lower values of the corresponding ranges within the regions to identify a region in the first sorted list, wherein all of the preceding regions in the first sorted list could include the point, the first sublist comprising the identified region and all of the preceding regions in the first sorted list; (d) repeating step (c) using the upper values of the ranges instead of the lower values and the second sorted list instead of the first sorted list, and creating a second sublist of the second sorted list where the point could be located, the second sublist comprising a region identified in the second sorted list, and all of the regions succeeding the identified region in the second sorted list; (e) comparing the first sublist with the second sublist to determine which sublist is the shorter, or if the sublists are equal in length; (f) selecting the shorter sublist to linearly search, and if the sublists are equal in length, selecting either sublist; and (g) linearly searching the selected sublist until an item in the selected sublist is found where each coordinate for the point falls within each corresponding range within the region.

Claim 2

A method for computer sorting and making a search of a plurality of regions, each region expressed as at least one range, each range having a lower and an upper value, wherein the lower and upper values may be equal, and no two regions have both the same number of ranges and all corresponding ranges overlap, and wherein the search will determine whether a point, expressed as a plurality of coordinates, is included within one of the regions, the search being successful when both the number of coordinates of the point is equal to the number of ranges in a region and each coordinate of the point is within each corresponding range within the region, comprising the steps of: (a) creating a first sorted list of the regions by: (i) arranging the regions by the number of ranges within each region, and (ii) sub-arranging the regions having an equal number of ranges by the lower value of the first range in each region, and for regions having an equal number of ranges and an equal lower value for the first range, proceeding to a comparison of the lower value for each successive corresponding range in the regions until two corresponding lower values are unequal; (b) creating a second sorted list of the regions by repeating step (a) using the upper values for the ranges instead of the lower values; (c) performing a preliminary search on the first sorted list to create a first sublist of regions where the point could be located, searching first for regions that have the same number of ranges as the point has coordinates, and thereafter searching said regions having the same number of ranges as the point has coordinates, by comparing coordinate values of the point with the lower values of the corresponding ranges within the regions to identify a region in the first sorted list, wherein all of the preceding regions in the first sorted list could include the point, the first sublist comprising the identified region and all of the preceding regions in the first sorted list; (d) repeating step (c) using the upper values of the ranges instead of the lower values and the second sorted list instead of the first sorted list, and creating a second sublist of the second sorted list where the point could be located, the second sublist comprising a region identified in the second sorted list, and all of the regions succeeding the identified region in the second sorted list; (e) comparing the first sublist with the second sublist to determine which sublist is the shorter, or if the sublists are equal in length; (f) selecting the shorter sublist to linearly search, and if the sublists are equal in length, selecting either sublist; and (g) linearly searching the selected sublist until an item in the selected sublist is found where each coordinate for the point falls within each corresponding range within the region.