Hi, I wonder if anyone could help me solve this problem. I have a certain dataset of n-tuples x=(x_1,x_2,x_3,...,x_d). I want to efficiently repeatedly select 'rectangles' in this dataset. i.e. I want all points which lie within x_low=(xlow_1, xlow_2, .... xlow_d) x_hi=(xhi_1,xhi_2,... xhi_d).
In 1d (i.e. I just have 1-tuples) it's not a problem: -first store the data in an array or vector etc. -sort the array. -whenever I want a region do a binary search for x_low, x_hi (O(log N) where N is the size of dataset) How do I extend this to selecting in 2 or more dimensions? The only extension I can think of is not very good: -first sort the data based on the first position in the n-tuple (xA<xB if xA_1<xB_1) -whenever I want data within a rectangle I do a binary search based on the first entry in the ntuple and select a 'band' in the data i.e all points with x_1 such that: xlow_1<x_1<xhi_1. -than I iterate through this band linearly and keep only the points with x_k such that: xlow_k<x_k<xhi_k. Selecting a rectangle is O(log N * M) where M is the number of datapoints in the 'band'. Anyone know of anything better? thanks, Wojtek --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
